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

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

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

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

Answer 6

 
   /*
* Steps Fibonacci recursion
* 1) 3 gets passed. (3 is printed to the screen during this call)
* 2) Fibonacci A gets decrements by 2 and recursion happens passing 1 as a param. (1 is printed to the screen during this call)
* 3) Fibonacci A hits the base case returning 1 and it "unwinds". (No recursion here)
* 4) Fibonacci B gets called, decrementing the previous value of n (3 was the previous value of n before A made the returning call) to 2. (2 is printed to the screen during this call)
* 5) Fibonacci A is called again subtracting 2 from n (2-2=0) and passes 0 as a param. (1 is printed to the screen during this call since it's converted from 0)
* 6) Fibonacci A hits the base case and "unwinds" (no recursion here)
* 7) Fibonacci B is called subtracting 1 from 2 (2 was the previous value of n before A made the returning call) and passes 1 as a param. (1 is printed to the screen during this call)
* 7) Fibonacci B now hits the base case, returning 1 and "unwinds" (no recursion here)
* 8) Fibonacci B retraces it's steps back through All previous fucntion calls and values of n (n=2 in our case) and adds [them] to the copy of n=1 stored in its local scope
* 9) Once Fibonacci B completes the "unwinding" process, it returns the calculated value to the original caller (no recursion here)

 Note* 
    Each instance of Fibonacci recursion creates its own scope and stores the returned value in a copy of n (in our case 1). 
    As it the function "unwinds" it executes subsequent code that receive the value of n at that time. (all functions that call other functions "unwind" back through previous calls once they return)

    In the last call of our Fibonacci example, Fibonacci B receives the value of n=2 as Fibonaccci A "unwinds" since that was the last value before it made the returning call.
    Once Fibonacci B reached the base case and "unwound", it retraced its steps back through all previous values of n (in our case just n=2) and added [them] to its local copy of n=1.

* The result when passing the number 3 is: 
                3
                 1
                 2
                  1
                  1
            (3)
*/

var div = document.getElementById('fib');

function fib( n, c ) {
  var indent = "";
  for (var i = 0; i < c; i++) {
    indent += " ";
}
  var v = n===0 ? 1 : n
  var el = document.createElement('div'),
  text = indent + "fibonacci(" + v + ")";
  el.innerHTML = text;
  div.appendChild(el);
  if(n<2){
     return 1;
  } 
  return fib(n-2, c + 4)  + fib(n-1, c + 4);

}

Answer 7

The function is calling itself. That's simply the definition of a recursive function. In the 5th line it is transferring execution to itself by passing parameters that will result in a value.

To ensure that a recursive function doesn't turn into an endless loop, there must be some sort of condition that doesn't call itself. The goal of your code in the question is to perform the calculations of a fibonacci sequence.

Answer 8

To calculate nth fibonacci number, the relation is F(n) = F(n-2) + F(n-1).

If we implement the relation in the code, for nth number, we calculate the (n-2)th and (n-1)th number using the same method.

Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2. As recursive functions need a stop condition to stop recursing, here n<2 is the condition.

f(7) = F(6) + F(5);

in turn, F(6) = F(5) + F(4)

F(5) = F(4) + F(3)...

it goes on until n<2

F(1) returns 1

Answer 9

It is going to cascase like this:

7 - 2 = 5 --> fibonacci(5)
7 - 1 = 6 --> fibonacci(6)

Like given in the implement the left hand side will always decreases by

2 and the right hand decreases by 1, so it will cascade this way until it hits 1, once it hits 1 it will add it up to the outputs of the right hand function 1 + fibonacci(n-1);, which as well will always stop at 1's as per the implementation:

if (n < 2){
  return 1;
}

Eventually they all end up having 1's in memory and start adding them up from left to right... consider the cascading representation below, adding up all 1's at the bottom will make it 21.

if n > 2______________Left always n - 2 __________&____________Right always n - 1 ________else n = 1

                                        7
                   
                        5                              6
                   3          4                  4              5
                 1    2    2     3            2     3      3        4
               1     1 1  1 1  1   2         1 1  1  2   1  2    2    3
                                  1 1               1 1    1 1  1 1  1  2
                                                                       1 1

               1+    1+1+ 1+1 1+  1+1+       1+1+ 1+1+1+ 1+1+1+ 1+1+ 1+1+1 = 21

7th position in Fibonacci sequence is 21, we can test it with array:

const fibArray = [1, 1, 2, 3, 5, 8, 13, 21]
console.log(fibArray[7]) //-> 21

Answer 10

Fibonacci algorithm with recursive function based on ES6

const fibonacci = ( n, k = 1, fib2 = 0, fib1 = 1 ) => {
  return k === n ? 
    (() => { return fib1; })() 
    : 
    (() => {
      k++;
      return fibonacci(n, k, fib1, fib1 + fib2);
    })();  
}
console.info(' fibonacci ' + 11 + ' = ' + fibonacci(11));

Answer 11

look, fib is

t(n) = t(n - 1) + n;

if n = 0 then 1

so let see how recursion works, I just replace n in t(n) with n-1 and so on. it looks:

t(n-1) = t(n - 2) + n+1;

t(n-1) = t(n - 3) + n+1 + n;

t(n-1) = t(n - 4) + n+1 + n+2 + n;

.

.

.

t(n) = t(n-k)+ ... + (n-k-3) + (n-k-2)+ (n-k-1)+ n ;

we know if t(0)=(n-k) equals to 1 then n-k=0 so n=k we replace k with n:

t(n) = t(n-n)+ ... + (n-n+3) + (n-n+2)+ (n-n+1)+ n ;

if we omit n-n then:

t(n)= t(0)+ ... + 3+2+1+(n-1)+n;

so 3+2+1+(n-1)+n is natural number. it calculates as Σ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

the result for fib is : O(1 + n²) = O(n²)

This the best way to understand recursive relation

Answer 12

Sharing a simpler code for fib in JS/ES6 using recursion.

function fib(n, first = 1, second = 1) {
    if (n <= 2) return 1;
    [first, second] = [second, first + second];
    return (n - 2 === 1) ? second : fib(n - 1, first, second);
}

console.log(fib(10));

Answer 13

I have written the same code in more concise way.

const prompt = require("prompt-sync")();

function Fibonacci(count, num_1 = 0, num_2 = 1) {
    if (count == 0) {
        return;
    }
    console.log(num_1);
    fibonacci(--count, num_2, num_1 + num_2)
}
const iteration = parseInt(prompt("Enter Count: "))
Fibonacci(iteration);

Check it Out.

Answer 14

I find it helpful to visualize the callstack. Not sure if this is exactly what the callstack would look like for this recursive function execution (likely its not) but its a rough idea that helps me understand the process more clearly. Plus symbols for example are not on the stack like this, and are evaluated at the call site (correct me if i'm wrong). Not sure how the addition actually is computed in terms of the callstack. Here is a callstack visualization diagram, helped clarify a lot of things for me in terms of the full function execution flow, and encompasses tree diagrams as well

here is an excalidraw link that will allow more zoom clarity

recursive fibonacci callstack

Open to any feedback on improving this, thanks :)