# 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.

See also Tail Recursion.