Alex Rivera | Logout

How does the fibonacci recursive function "work"?

Asked 2012-01-13T02:25:36.383
83

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?

recursion fibonacci
Edit
Report

1 Answer

25

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.

answered 2012-01-13T02:51:16.403

Your Answer