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?

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

Answer 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)    };