Recursive Functions for Beginners

#beginners #tutorial #ruby

If you have arrived on this page you are probably struggling with the concepts of recursion. You aren't alone. As programmers, we first learn the basic iterative loop structure. When asked to accomplish the same task with recursion I found it difficult to know where to begin. I choose to write on this topic to force myself to learn more on the subject and gain practice writing recursive functions!

Recursive functions are essentially the same as iterative loops. They both do a procedure repeatedly but in a different way. Instead of using each, while, for or do loops a recursive function repeats a process by calling itself. But what do I mean by call itself? Let's look at some examples...

Below is a traditional while loop that will display a message to tell the user "The cat is still hungry" until there are no more cans of food left.

def feedCat(cans_of_food)
  while cans_of_food > 0
    puts "The cat is still hungry"
    cans_of_food -= 1
  end
  puts "There are no more cans of food, the cat is full... hopefully"
end

feedCat(4) #feed your cat 4 times to make them full!

By making some small tweaks we can write the same function using recursion

def feedCat(cans_of_food)
  if cans_of_food > 0 # recursive case
    puts "cat is still hungry"
    feedCat(cans_of_food - 1)
  end
  # base case, cans_of_food <= 0
  puts "There are no more cans of food, the cat is full... hopefully" 
end

feedCat(4)

You can see that the code actually looks very similar to the iterative loop above. Instead of the code returning to the top of the "when" loop, the function CALLS ITSELF again. I would like to point out that if we had not added the decrement of cans_of_food in the parameters of the recursive call we would be stuck in an infinite loop. The cat would continuously be fed, the cans of food would never diminish.... actually I think the cat would enjoy that ....

Converting Iteration into Recursion

Rule of thumb: If you are stuck build your iterative loop first!

Replace beginning of loop with if conditional
In the above example while cans_of_food > 0 was changed to if cans_of_food > 0
This is the recursive case. It tells you the condition in which you would keep going.
Replace iterative variable line with the recursive call
In the above example cans_of_food -= 1 was changed to feedCat(cans_of_food - 1)
Identify the base case, also known as the end condition. The base case is very similar to the conditional of the iterative loop. Without it, the function would repeat forever!! In the above example the base case is *if cans_of_food <= 0 *. We could also write our recursive function to have the base case first!

def feedCat(cans_of_food)
  if cans_of_food <= 0 # base case
    puts "There are no more cans of food, the cat is full... hopefully"
  else #recursive case, cans_of_food > 0
    puts "cat is still hungry"
    feedCat(cans_of_food - 1)
  end 
end

feedCat(4)

This syntax may not always translate exactly but it is a good guide to help new "recursers".

The cat feeding examples above would be classified as direct recursion because the method only calls itself. There are also indirect recursive functions where one function calls a second, which calls a third which then calls the first again.

Not All Rectangles Are Squares

All iterative loops can be made into recursive functions. However, not ALL recursive functions can be iterative loops, or they are at least VERY complex. You won't find recursion in simple applications. However, they can be particularly useful in mathematical programming, searching algorithms and compilers.

Below we have the Starbucks drink of examples.... the Fibonacci sequence example. The fib goes 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 ... etc. add the pervious 2 numbers together to get the current sum.

def fib(num)
  if num > 1 #recursive case
    return fib(num - 1) + fib(num - 2)
  end
  return num #base case, num <= 1
end

puts fib(10)

Another common example is the factorial function. If given factorial of 6 you do 6 * 5 * 4 * 3 * 2 * 1 = 720. Below is how you can solve this mathematical equation using recursion.

def fact(num)
    if num <= 1
        return n
    else
        return n * fact(n - 1)
    end
end

puts fact(6)

Anything you can do I can do... more expensively?

Consider your options when choosing iteration vs recursion. The basic idea is that with each recursive call it costs you time and space which can be precious. So consider potential performances issues when selecting which route to take. Click here to learn more from Abinoda!

Interesting Behavior

I did not know about this behavior until playing around with the code. In an iterative loop version of the code snippet below, you would expect the output to look like 10, 9, 8, 7 ... etc. By clicking the run button we can see that the lowest number 0 is displayed first.

This is because the puts tries to display a value it must finish evaluating the ALL the method calls first. It tries to print, says okay we have to figure out the value of printNum(num - 1). It must then preform printNum(num - 1) until it reaches the base case. I like to think of this as going deeper into the layers of code. Like how you can drill deeper into the earth's layers to near the earth's core. On the last call of printNum num is 0. At the point the function print the first value it receives, 0 (the codes "core"). So it prints 0 then works it ways back up the layers of code.

Recursive layers kind of preform in the first in - last out (FILO), aka a stack. So the num 10 was the first value we passed into * puts printNum(num - 1)* but 10 printing the value 10 was the last operation!

I hope this small demo and examples helped you understand recursion!

To get a little history lesson on recursion from a charming gentleman! follow the link!