How does the fibonacci recursive function "work"?

Question

I'm new to Javascript and was reading up on it, when I came to a chapter that described function recursion. It used an example function to find the nth number of the Fibonacci sequence. The code is as follows:

function fibonacci(n) {
    if (n < 2){
        return 1;
    }else{
        return fibonacci(n-2) + fibonacci(n-1);
    }
}

console.log(fibonacci(7));
//Returns 21

I'm having trouble grasping exactly what this function is doing. Can someone explain what's going on here? I'm getting stuck on the 5th line, where the function calls itself. What's happening here?

Solution 1

You're defining a function in terms of itself. In general, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1). We're just representing this relationship in code. So, for fibonnaci(7) we can observe:

• fibonacci(7) is equal to fibonacci(6) + fibonacci(5)
• fibonacci(6) is equal to fibonacci(5) + fibonacci(4)
• fibonacci(5) is equal to fibonacci(4) + fibonacci(3)
• fibonacci(4) is equal to fibonacci(3) + fibonacci(2)
• fibonacci(3) is equal to fibonacci(2) + fibonacci(1)
• fibonacci(2) is equal to fibonacci(1) + fibonacci(0)
• fibonacci(1) is equal to 1
• fibonacci(0) is equal to 1

We now have all the parts needed to evaluate fibonacci(7), which was our original goal. Notice that the base case -- return 1 when n < 2 -- is what makes this possible. This is what stops the recursion, so that we can can start the process of unrolling the stack and summing the values we're returning at each step. Without this step, we'd continue calling fibonacci on smaller and smaller values right up until the program finally crashed.

It might help to add some logging statements that illustrate this:

function fibonacci(n, c) {
    var indent = "";
    for (var i = 0; i < c; i++) {
        indent += " ";
    }
    console.log(indent + "fibonacci(" + n + ")");
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
    }
}

console.log(fibonacci(7, 0));

Output:

fibonacci(7)
    fibonacci(5)
        fibonacci(3)
            fibonacci(1)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
    fibonacci(6)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
        fibonacci(5)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
            fibonacci(4)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
                fibonacci(3)
                    fibonacci(1)
                    fibonacci(2)
                        fibonacci(0)
                        fibonacci(1)

Values at the same level of indentation are summed to produce the result for the previous level of indentation.

Solution 2

There are many good answers here, but I made this diagram which helps better explain the outcome of the function. The only values that will ever be returned are 1 or 0 (your example returns 1 for n < 2, but should instead return n).

This means that each recursive call will eventually wind up returning either a 0 or 1. Those end up being "cached" in the stack and "carried up" into the original invocation and added together.

So if you were to draw this same diagram out for each value of 'n' you could manually find the answer.

This diagram roughly illustrates how every function is returned for fib(5).

This shows the control flow, i.e. the order of execution for the functions. Remember code is always executed left->right and top-> bottom. So whenever a new function is called it is paused and then the next invocation occurs.

The following illustrates the actual control flow based on your original post. Please note the base condition is if (n <= 0) {return 0} else if (n <= 2) {return 1;} for simplification:

1. fib(5) {
    return fib(4) + fib(3);
2.   fib(4) {
      return fib(3) + fib(2);
3.     fib(3) {
        return fib(2) + fib(1);
4.       fib(2) {
A=        return 1;
         };
5.       fib(1) {
B=        return 1;
         };
C=      return 2; // (1 + 1)
       };
6.     fib(2) {
D=      return 1;
       };
E=    return 3; // (2 + 1)
     };
7.   fib(3) {
      return fib(2) + fib(1);
8.     fib(2) {
F=      return 1;
       };
9.     fib(1) {
G=      return 1;
       };
H=    return 2; // (1 + 1)
     };
I=  return 5; // (3 + 2)
   };

Solution 3

Step 1) When fibonacci(7) is called imagine the following (notice how I changed all the n's to 7):

function fibonacci(7) {
    if (7 < 2){
        return 1;
    }else{
        return fibonacci(7-2) + fibonacci(7-1);
    }
}

Step 2) Since (7 < 2) is obviously false, we go to fibonacci(7-2) + fibonacci(7-1); which translates to fibonacci(5) + fibonacci(6); Since fibonacci(5) comes first, that get called (changes the n's to 5 this time):

function fibonacci(5) {
    if (5 < 2){
        return 1;
    }else{
        return fibonacci(5-2) + fibonacci(5-1);
    }
}

Step 3) And or course fibonacci(6) also gets called, so what happened is for everyone call of fibonacci 2 new fibonacci get called.

Visualization:

      fibonacci(7)
      ____|_____
     |          |
fibonacci(5)  fibonacci(6)
____|____     ____|_____
|        |    |         |
fib(3)  fib(4) fib(4)   fib(5)

See how it branches? When is it going to stop? When n becomes less than 2, thats why you have if (n < 2). At that point the branching stops and everything gets added together.

Solution 4

Hopefully the following helps. Calling:

fibonacci(3)

will get to line 5 and do:

return fibonacci(1) + fibonacci(2);

the first expression calls the function again and returns 1 (since n < 2).

The second calls the function again, gets to the 5th line and does:.

return fibonacci(0) + fibonacci(1);

both expressions return 1 (since n < 2 for both), so this call to the function returns 2.

So the answer is 1 + 2, which is 3.

Solution 5

These two functions gave me a much clearer explanation of recursion (from this blog post):

function fibDriver(n) {
  return n === 0 ? 0 : fib(0, 1, n);
}
 
function fib(a, b, n) {
  return n === 1 ? b : fib(b, a + b, n-1);
}

// Get the 10th fibbonacci number (when excluding the 0)
console.log(fibDriver(10))

View more solutions

Comments

[opes]

This nailed it for me. The flow that you created is just what I needed to make sense of it. Brilliant work.

[opes]

That makes sense. So basically every time the function is called, it will drill down to fibonacci(0) + fibonacci(1), which is 1 + 2 - where the actual math is being done. Thanks!

[Jesse Good]

Yeah, using console.log is a lot faster than trying to make a chart by hand like I did!

[opes]

Very nice. These diagrams are really helpful in grasping the concepts. I think that's where I was a bit fuzzy. Thanks for this!

[four-eyes]

What I wonder: If n becomes less than 2, shouldn't the condition to return 1 be then fulfilled? Why doesn't it return `2?

[Jesse Good]

@Chrissl: From here: *By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1,* depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two. It returns 1 because that is how the sequence is defined.

[four-eyes]

@JesseGood Yes, I understand that. But you wrote When is it going to stop? When n becomes less than 2, thats why you have if (n < 2). At that point the branching stops and everything gets added together. Why does it add together? The statement says if (n < 2) { return 1;

[Jesse Good]

@Chrissl: fibonacci(7-2) + fibonacci(7-1) Do you see the + sign between the two fibonacci calls? The returned values from fibonacci(7-2) and fibonacci(7-1) are added together. (This is just one example) What is the returned value? Well, that happens at the return statements and when n is less than 2, 1 is returned.

[Mattias]

Great visualization! Even though I already know how recursive calculation works, I must say that this gives an excellent visual representation of how the actual sum is being calculated. Thumbs up!

[Mikeumus]

The accepted answer may be a good example of recursion and the stack but this answer is much more efficient in practice.

[Juan]

If you are looking for a functional way to cache the results to optimise the function calls const fibonacci = (n, cache = {1: 1, 2: 1}) => cache[n] || (cache[n--] = fibonacci(n--, cache) + fibonacci(n, cache));

[Vitaliy Terziev]

Shouldn't "fibonacci(0) is equal to 1" instead be equal to 0 in your example above?

[Wayne]

It is (unless I'm missing something). Is there somewhere that I say otherwise?

[Vitaliy Terziev]

Hm maybe I am missing something then because I can clearly see "fibonacci(0) is equal to 1" in your observation just blow the start of your answer (bullet-point 8). I thought that when input n=0 the recursive function should return n i.e. 0.

[Vitaliy Terziev]

Apart from this minor typo this is by far the best explanation one could possibly find one the world wide web.. (which is something..) great work!

[Mote Zart]

Very good answer. The Since fibonacci(5) comes first, that gets called & And or course fibonacci(6) also gets called, these are what helped me understand how the return can be two function calls. I'll have to trust you that his is actually what is happening under the hood ;)