Understanding Recursion (Fibonacci Sequence)

Recursion can be tricky even for experienced developers. I’ll try to explain to the best of my understanding how it works using the usual suspect: the Fibonacci sequence.

Fibonacci Sequence

In mathematics, the Fibonacci sequence is described as follow:

Fibonacci sequence is a sequence of numbers where each subsequent number is the sum of the previous two numbers in the sequence, except for the first two numbers, namely 0 and 1.

The sequence can be written like this:

$$ F_{n} = \begin{cases} 0 & \quad \text{, } n = 0 \\ 1 & \quad \text{, } n = 1 \\ F_{n-1} + F_{n-2} & \quad \text{, } n > 1 \end{cases} $$

The beginning of the sequence is thus:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…

How it Translates in Programming

We can write this sequence in Ruby using a recurion, like the code shown below.

def fibonacci(n)
  return 1 if n <= 2
  fibonacci(n - 1) + fibonacci(n - 2)
end

The conundrum is on line three, when the method calls itself twice on the same line.

This is what is called recursion: a method or function which calls itself until a return condition is reached.

In the code above, the exit condition is on line two: if n <= 2.

Let’s look at what happens when we n = 3 ($F_{3}$):

We know that $F_{3} = F_{2} + F_{1}$ ; let’s see how it works:

$$ \begin{split} F_{3} = F_{2} + F_{1} \\ F_{3} = (F_{1} + F_{0}) + F_{1} \\ F_{3} = (1 + 0) + 1 \\ F_{3} = 2 \end{split} $$

Summary

The final return value of the requested Fibonacci number comes from the last line of our code: fibonacci(n - 1) + fibonacci(n - 2).
The line return if n <= 2 is executed only during the recursion when $F_{n} > 1$ is to be calculated.
The method needs to know what the previous two answers ($F_{n-1}$ and $F_{n-2}$) are before behing able to calculate $F_{n}$. In other words, in every case the procedure works its way down to n == 1 and then builds the final result with each return.
The Fibonacci joke is worse than the last two jokes you heard, combined.