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:

• Pass int to the function and check if it's 0 or 1
• If it's 0 or 1, proceed to return the passed value
• If it's not 0 or 1, minus 1 from 7, then minus 2 from 7
• Return the output which according through my (obviosly faulty) thinking would be 11

How does the function e to the result of 13?

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:

• Pass int to the function and check if it's 0 or 1
• If it's 0 or 1, proceed to return the passed value
• If it's not 0 or 1, minus 1 from 7, then minus 2 from 7
• Return the output which according through my (obviosly faulty) thinking would be 11

How does the function e to the result of 13?

• javascript

• 4 You should learn about recursion that's what happening here. developer.mozilla/en-US/docs/Glossary/Recursion – Krusader Commented Oct 15, 2017 at 12:38
• The function is unnecessarily hard to read. Would you appreciate a re-written form that's more readable? – glhrmv Commented Oct 15, 2017 at 12:41
• 15 @glhrmv Sorry, but how is this hard to read? It's a simple ternary operator. – anon Commented Oct 15, 2017 at 12:43
• 3 Well it's easier to step through how something is working if it's on multiple lines, as opposed to jumbled up into one. Good luck using the debugger statement with this. – glhrmv Commented Oct 15, 2017 at 12:49
• 2 according to your function fib(7) = fib(6) + fib(5) if you put the values in there its fib(7) = 8 + 5 = 13 , how did you find 11 ? – Ömer Erden Commented Oct 15, 2017 at 12:53

4 Answers 4

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

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!!

Wele 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 remend 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.

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

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://posingprograms./pages/28-efficiency.html)