How does the recursive Fibonacci function work?

Question

I am new to Javascript and reading on it when I came to the chapter that describes the recursion function. He 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 am having trouble understanding what this function does. Can someone explain what is going on here? I am stuck on the 5th line where the function calls itself. What's going on here?

Answer 1

You define a function in terms of yourself. In general, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1) . We simply represent this relationship in code. So, for fibonnaci(7) you 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 1
• fibonacci(0) is 1

Now we have all the parts necessary to evaluate fibonacci(7) , which was our initial goal. Note that the main case - return 1 , when n < 2 - makes this possible. This is what stops recursion, so we can start the process of expanding the stack and summarize the values ​​that we return at each step. Without this step, we continue to call fibonacci smaller and smaller values ​​until the program crashes completely.

This can help add a few 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 indentation level are summed to produce the result for the previous indentation level.

Answer 2

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

This means that each recursive call will ultimately return either 0 or 1. Ultimately, they are "cached" on the stack and "wrap" to the original call and added together.

So, if you were to draw the same diagram for each "n" value, you could manually find the answer.

This diagram roughly illustrates how each function returns for fib (5).

This shows the control flow, that is, the execution order for functions. Remember that code always runs on the left-> right and on the top-> bottom. Therefore, whenever a new function is called, it pauses, and then the next call occurs.

Below is the actual control flow based on your original message. Note that the basic condition is if (n <= 0) {return 0} else if (n <= 2) {return 1;} to simplify:

 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 (note how I changed all n 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 into fibonacci(5) + fibonacci(6); Since fibonacci(5) in the first place that gets called (changes n to 5 this time):

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

Step 3) And the fibonacci(6) call is also called, so what happened to call all fibonacci 2 new fibonacci .

Visualization:

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

See how it goes? When will he stop? When n gets less than 2, that's why you have if (n < 2) . At this point, the branching stops and everything comes together.

Answer 4

Hope the following helps. Vocation:

 fibonacci(3) 

go 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 into the 5th line and does :.

 return fibonacci(0) + fibonacci(1); 

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

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

Answer 5

I think these two functions gave me a clearer explanation of recursion (from this 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); } 

Answer 6

To calculate the nth Fibonacci number, the ratio F (n) = F (n-2) + F (n-1).

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

Each subsequent number is the sum of the two previous 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 if n> 2. Since recursive functions require a stop condition to stop recursion, here n <2 is a condition.

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

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

F (5) = F (4) + F (3) ... it continues until n <2

F (1) returns 1

Answer 7

The function calls itself. This is just a definition of a recursive function. In the 5th line, this is passing the execution to itself by passing parameters that will lead to the value.

To ensure that the recursive function does not turn into an infinite loop, there must be some condition that does not call itself. The purpose of your code in the question is to perform Fibonacci sequence calculations.

Answer 8

 
    / *
 * 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 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 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
                  one
                  2
                   one
                   one
             (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 9

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 10

look fiction

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

if n = 0, then 1

so let's 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 (nk) + ... + (nk-3) + (nk-2) + (nk-1) + n;

we know that if t(0)=(nk) is 1 then nk=0 therefore n=k we replace k with n :

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

if we omit nn then:

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

therefore 3+2+1+(n-1)+n is a positive integer. calculated as Σ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

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

This is the best way to understand a recursive relation.