CODEWITHSUNDEEP
javascript
anon
anon

Reputation:

Stuck on a simple fibonacci with Javascript

I don't seem to understand the output of this block of code:

function fib(x) {
  return (x === 0 || x === 1) ? x : fib(x - 1) + fib(x - 2);
}

fib(7);
// output is 13

Here's my thinking process:

How does the function come to the result of 13?

Upvotes: 5

Views: 938

Answers (4)

Miraj50
Miraj50

Reputation: 4407

If it's not 0 or 1, minus 1 from 7, then minus 2 from 7 Here is the fault. It will recurse, stacks will be built up (Meaning more fib() functions will be called). If you would like a pen and paper solution, here it is. Everything is done from left to right, mind that. I have shown a simple example for x=4. Try extending it for x=7. Will make the concept of recursion clearer to you!!

Fibonacci Recursion

Upvotes: 3

Pac0
Pac0

Reputation: 23174

You just forgot that what is returned if fib(6)+fib(5), not 6+5

This schema can help you understand the logic and order of calculations for fib(5) :

recursive Fibonacci function for fib(5)

Try to draw the same diagram for fib(6), and then for fib(7), and you will understand recursion much better.

And also quickly conclude that this is a terribly inefficient algorithm to use if your goal is actually calculating Fibonacci numbers

(taken and modified image from an other answer of mine on a related question, diagram originally from http://composingprograms.com/pages/28-efficiency.html)

Upvotes: 0

Markus
Markus

Reputation: 182

Welcome to the beautifull world of recursion. It may be a hard concept to grasp, but very rewarding when you finally understand it.

@Elif A have written a nice table which shows exactly how the program run. However, when I learned recursion myself, I had this strategy where I "mapped" all the inputs on a piece of paper, starting with the inputs which gave me a value, instead of a function call. Then I build my way up. I really recommend this strategy, if you have a hard time understanding recursion.

Consider the following code

function factorial(n) {
      if (n == 1) {
             return 1;
       }
       else {
             return n*factorial(n-1)
       }
}

Lets say we want to find factorial(5). Instead of starting from the top, evaluating factorial(5), lets start at the bottom, building our way up to factorial(5). You'll see why this is a good intuitive way of understanding recursion.

factorial(1) = 1

factorial(2) = 2 * factorial(1) = 2 * 1 = 2

factorial(3) = 3 * factorial(2) = 2 * 3 = 6

factorial(4) = 4 * factorial(3) = 4 * 6 = 24

factorial(5) = 5 * factorial(4) = 5 * 24 = 120

Again, let me precise that this is just a way of understanding recursion. The table, which I mentioned is how the program actually run, and do the recursion.

Upvotes: 1

Elif A.
Elif A.

Reputation: 136

--------------------------------------------------------------
| Step  | Function | Result                                 |
--------------------------------------------------------------
|  1    | f(7)     | f(6) + f(5) = a
|  2    |   a      | [f(5)+f(4)] + [f(4)+f(3)] = b
|  3    |   b      | [ [f(4)+f(3)] + [f(3)+f(2)] ] + [ [(f(3)+f(2)] + [f(2)+f(1)] ] = c
|  4    |   c      | [ [ [f(3)+f(2)] + [f(2)+f(1)] ] + [ [f(2)+f(1)] + [f(1) + f(0)] ] ] + [ [ [f(2)+f(1)]  + [f(1) + f(0)] ] + [ [f(1) + f(0)] + 1] ] = d
|  5    |   d      | [ [ [ [f(2)+f(1)]  + [f(1) + f(0)] ] + [ [f(1) + f(0)] +1] ] + [ [ [f(1) + f(0)] +1] + [1 + 0] ] ] + [ [ [ [f(1) + f(0)] +1]  + [1 + 0] ] + [ [1 + 0] + 1] ] = e
|  6    |   e      | [ [ [ [ [f(1) + f(0)] +1]  + [1 + 0] ] + [ [1 + 0] +1] ] + [ [ [1+ 0] +1] + [1 + 0] ] ] + [ [ [ [1 + 0] +1]  + [1 + 0] ] + [ [1 + 0] + 1] ] = f
|  7    |   f      | [ [ [ [ [1 + 0] +1]  + [1 + 0] ] + [ [1 + 0] +1] ] + [ [ [1+ 0] +1] + [1 + 0] ] ] + [ [ [ [1 + 0] +1]  + [1 + 0] ] + [ [1 + 0] + 1] ] = g

g= 13

Upvotes: 5

Related Questions