I am currently enrolled at Launch School in order to learn the art of programming. During the section where we learn about recursion, the Fibonacci sequence is used to illustrate the concept.

Below is a recursive method, written in Ruby, to find the nth number in the Fibonacci sequence. I will attempt to explain how this method works using the code as well as a tree diagram as presented in the Launch School course.

In maths, the Fibonacci sequence is described as: the sequence of numbers where the first two numbers are 0 and 1, with each subsequent number being defined as the sum of the previous two numbers in the sequence.

The Fibonacci sequence looks like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 and so on.

Take a look at the code shown below. Even if you do not know Ruby at all, it should make some sense to you. The mind-twisting part (for those new to programming) comes in where the code inside the fibonacci() method calls itself not once but twice (3rd last line)!

This is of course what recursion is. A method or function that calls itself until some exit condition is reached. The exit condition here is the first part of the ‘if’ statement and is met when the method variable number is smaller than 2.

# fibonacci.rb
def fibonacci(number)
  if number < 2
    number
  else
    fibonacci(number - 1) + fibonacci(number - 2)
  end
end

To start with, let’s also look at the tree structure in the diagram below:

Fibonacci Diagram

For now, only look at the leftmost three blocks. The ones that have f(2) and then under that f(1) and f(0).

This is the small tree for fibonacci(2), i.e. for finding the 2nd element in the Fibonacci sequence (we start counting at 0).

We begin by feeding the fibonacci method the value of 2, as we want to calculate fibonacci(2). You can see from the method code that we end up in the ‘else’ section of the ‘if’ statement (as number = 2, which is not smaller than 2).

The following line of code is now about to be executed:

fibonacci(number - 1) + fibonacci(number - 2)

Replace ‘number’ with the value 2 and the line of code becomes:

fibonacci(1) + fibonacci(0).

The next step is to find the values of the two terms, fibonacci(1) and fibonacci(0). The computer will need to call the fibonacci method for each of these two terms. This is where the recursion comes in.

In order to do the evaluation and make use of the fibonacci method, while the program is already currently inside the fibonacci method, the computer will store the current state or instance of the fibonacci method (we can call this instance ‘fibonacci(2)’ ), and then evaluate fibonacci(1). It will get a result of 1 because of the two lines of code shown below, and with number = 1. In Ruby the code do not have to read “return number”, it only needs to state the variable whose value is to be returned. Hence, number is returned as can be seen in the 2nd line below (which will return 1 in this case).

if number < 2
  number

Ruby will store this value as the result of fibonacci(1), and continue to evaluate fibonacci(0). The same two lines of code above will result in a value of 0 (zero) when fibonacci(0) is evaluated.

There are no more recursion operations left to do as both terms in the line of code have been resolved to actual values:

fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1

On the tree structure in the diagram, we have resolved f(0) = 0 and also f(1) = 1. This allows us to resolve f(2), which is f(1) + f(0) = 1.

It may help to think in terms of the time dimension and different ‘instances’ of the fibonacci method here. Each time a recursive call is made to the fibonacci method, the current state, or instance, of the method is stored in memory (the stack), and a new value is passed to the method for the next instance of the method to use. As each term is resolved to the value 0 or 1, the previous instance of the method can be resolved to an actual value. The result is that the line of code:

fibonacci(number - 1) + fibonacci(number - 2)

can now be resolved by adding the two values. This result is then returned to the previous instance of the fibonacci method in order to again help with the line of code’s resolution to actual values in that instance. The adding of the two terms continue in this manner, until all the terms in the equation is resolved to actual values, with the total then returned to the code which called the fibonacci method in the first place.

As an example, if we wanted to calculate fibonacci(3), we know from the definition of the Fibonacci sequence that:

fibonacci(3) = fibonacci(2) + fibonacci(1)

And, using the recursive method, we get to the line of code above which reflects this definition:

fibonacci(2) + fibonacci(1)

fibonacci(2) is further recursively resolved to:

(fibonacci(1) + fibonacci(0)) + fibonacci(1)

Which leads us to the end result:

fibonacci(3) = (fibonacci(1) + fibonacci(0)) + fibonacci(1)

which evaluates/resolves to:

fibonacci(3) = 1 + 0 + 1 = 2

And, as we can see in the blocks shown in the corresponding tree structure:

f(3) = f(2) + f(1) = f(1) + f(0) + f(1) = 1 + 0 + 1 = 2

The tree structure diagram and its relation to the recursive fibonacci method should make more sense now. Recursion will happen till the bottom of each branch in the tree structure is reached with the resulting value of 1 or 0. During recursion these 1’s and 0’s are added till the value of the Fibonacci number is calculated and returned to the code which called the fibonacci method in the first place.

To recap:

The recursive method (algorithm) ‘unwinds’ the number you give it until it can get an actual value (0 or 1), and then adds that to the total. The “unwinding” takes place each time the value of ‘number-2’ and the value of ‘number-1’ is given to the fibonacci method when the line

fibonacci(number-2) + fibonacci(number-1)

is evaluated. Note that the value of ‘number-2’ in this case is the value of the next instance of the fibonacci method’s variable number (next recursive loop). The same goes for the value of ‘number-1’.

With each recursion where the method variable number is NOT smaller than 2, the state or instance of the fibonacci method is stored in memory, and the method is called again. Each time the fibonacci method is called though, the value passed in is less than the value passed in during the previous recursive call (by either 1 or 2). This goes on until the value returned is a value smaller than 2 (either 0 or 1). The resolution of the previous instance can then be done. In one instance, 0 is returned and fibonacci(0) can be resolved to 0. In another, 1 is returned and fibonacci(1) can be resolved to 1.

These values are then summed in order to obtain the requested Fibonacci number. This summing action happens each time a 0 or 1 is returned from one instance of the fibonacci method to the previous instance of the fibonacci method, and so on.

This is equivalent to where all the 1’s and 0’s at the bottom of the tree structure are added together. The final sum (or total) of all these 0's and 1's is then the value of the Fibonacci number requested in the first place. This value is returned during the final return of the fibonacci method to where the method was called from in the first place.

It is important to note that, except for the case where we want to know what the values of fibonacci(0) or fibonacci(1) is, the final return value of the requested Fibonacci number will come from the following line of code in the method:

fibonacci(number - 1) + fibonacci(number - 2)

Also note that in this scenario, where the value of any Fibonacci number greater than 1 is to be calculated, the lines of code:

if number < 2
  number

will only be used during the recursive process.

I hope my explanation did not confuse you further, but helped in your understanding of both what the Fibonacci sequence is, and how we use recursion in Ruby to calculate the numbers in the sequence.

PS: Hello everybody, I am glad if this post was of any help to you. I have received a few comments about the fact that this method of calculating the Fibonacci sequence is not optimal. I do realize that and I am sure the guys at Launch School do so as well!

I do appreciate those specific comments with references on how to calculate the sequence much more optimally, but to highlight the 2nd sentence in the post above: “During the section where we learn about recursion, the Fibonacci sequence is used to illustrate the concept.”. So it is just an example used to illustrate the concept of recursion.