Let’s talk about Recursion.

Recursion. What is it? It is where a solution to a problem depends on solutions to smaller instances of the same problem. Let’s use the Fibonacci Sequence for this article.

What is the Fibonacci Sequence?

In a Fibonacci sequence a number is the sum of its two preceding numbers. For example, 1 1 2 3 5 8. 8 is made up of 5 and 3, 5 is made up of 2 and 3, 3 is made up of 2 and 1, etc.

We can say, a number is equal to the sum of the number minus one and the number minus 2 in the sequence.

n = (n-1) + (n-2)

If we think this as a function we could do:

fib(n) = fib(n-1) + fib(n-2)

In ruby we could write:

def fib(n)
   return fib(n-1) + fib(n-2)
end

The issue we have at this point is we created an infinite loop. We need a base case.

def fib(n)
   #base case
   if n <= 1
      return n
   end
   
   return fib(n-1) + fib(n-2)
end

What are we looking at?

Let’s say we want to know what the 4th number in the Fibonacci is.

def fib(n)
   #base case
   if n <= 1
      return n
   end
   
   return fib(n-1) + fib(n-2)
end
print fib(4)

The 4 doesn’t meet the base case, so it will skip the if statement. We hit the return fib(n-1) which in this case is fib(4–1) which is fib(3). Since 3 doesn’t meet the base case, it will break down fib(3) to fib(n-1) + fib(n-2). It will first do fib(n-1) which is fib(2). It will keep calling itself till it meets the base case.

Let’s work out the left side of the tree first. We can see it will go all the way down to fib(2) = fib(1) + fib(0). Since the base case is n ≤= 1, fib(1) is 1 and fib(0) is 0. Therefore, fib(2) = 1 + 0. The second number in the Fibonacci Sequence is 1.

So now it will figure out what fib(1) is. As you can already see, an issue with Recursion is that it will keep solving the same problem even if its was solved previously. (Look for a future blog on dynamic programming and memoization.) But let’s keep going and see where it goes.

We know that fib(1) is = 1 so fib(3) = 1 + 1. The third number in Fibonacci is 2 so we’re looking good. Fibonacci = 1, 1, 2 , 3, 5.

Now we need to go up the right side of the tree.

So fib(4) = 3. The 4th number in the Fibonacci Sequence is 3.

Issues with Recursion

Recursion is slow. It also has greater space requirements. Why use it? It’s good to know and some data structure problems can only be solved through recursion.