What is the logic of the order of the calls, in recursion in Javascript?

Question

I have a hard time understanding the order of the calls in recursive programming in Javascript

While playing around with recursive programming in Javascript, I wanted to find a solution for the Fibonacci use case. The Fibonacci is just a use case to illustrate my question. But the question is about recursive programming in JS, not about the Fibonacci algorithm.

Given an index number N, return the corresponding value of the Fibonacci sequence, where the sequence is: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...).

Which I did with the following solution (I know I could improve it with memoization to avoid exponential complexity):

function fibonacci(n) {
  if (n <= 1) return 1;
  return fibonacci(n-1) + fibonacci(n-2);
}

---

As I wanted to understand it better, I started to add console.log() in my code. And that's when the mindfucking occurred 🤯.

The order of the calls, the enumerator and the steps don't make any sense to me!

function fibonacci(n, caller = 'initalFibonacciCaller', step = 0) {
  console.log(caller)
  console.log('n =', n)
  console.log('step =', step)
  console.log('----------------')

  if (n <= 1) return 1;
  step++
  return fibonacci(n-1, 'fibonacciCaller1', step) + fibonacci(n-2, 'fibonacciCaller2', step);
}

console.log('=>', fibonacci(4))

Response:

initalFibonacciCaller
n = 4
step = 0
----------------
fibonacciCaller1
n = 3
step = 1
----------------
fibonacciCaller1
n = 2
step = 2
----------------
fibonacciCaller1
n = 1
step = 3
----------------
fibonacciCaller2
n = 0
step = 3
----------------
fibonacciCaller2
n = 1
step = 2
----------------
fibonacciCaller2
n = 2
step = 1
----------------
fibonacciCaller1
n = 1
step = 2
----------------
fibonacciCaller2
n = 0
step = 2
----------------

5

How come that as from step3 fibonacciCaller2, the n start to increase and the steps start to decrease ?
This is probably due to my lack of understanding of how Javascript works, but I would love a good explanation on this.

Answer 1

Another way to visualize this, by adding a different flavor of logging than your steps, using an indentation parameter instead, gives a result like this:

fibonacci (4)
    left:
        fibonacci (3)
            left:
                fibonacci (2)
                    left:
                        fibonacci (1)
                        ==> 1    -- fibonacci (1) (base case)
                    right:
                        fibonacci (0)
                        ==> 1    -- fibonacci (0) (base case)
                ==> 1 + 1 ==> 2    -- fibonacci (2)
            right:
                fibonacci (1)
                ==> 1    -- fibonacci (1) (base case)
        ==> 2 + 1 ==> 3    -- fibonacci (3)
    right:
        fibonacci (2)
            left:
                fibonacci (1)
                ==> 1    -- fibonacci (1) (base case)
            right:
                fibonacci (0)
                ==> 1    -- fibonacci (0) (base case)
        ==> 1 + 1 ==> 2    -- fibonacci (2)
==> 3 + 2 ==> 5    -- fibonacci (4)

Returning 5

You can see from this that we proceed down the left-hand calls (the first recursive step) all the way before we back up a level and do the right-hand ones, back up another level and do its right-hand ones, etc.

You can see how I added the logging in this snippet:

const log = (indent, message) => 
  console.log (Array(indent * 2).fill('  ').join('') + message)

function fibonacci(n, indent = 0) {
  log (indent, `fibonacci (${n})`)
  if (n <= 1) {
    log(indent, `==> 1    -- fibonacci (${n}) (base case)`)
    return 1;
  }
  log (indent + 1, 'left:')
  const left = fibonacci(n-1, indent + 2) 
  log (indent + 1, 'right:')
  const right = fibonacci(n-2, indent + 2)
  const result = left + right;
  log(indent, `==> ${left} + ${right} ==> ${result}    -- fibonacci (${n})`)
  return result
}

console .log (``, `Returning ${fibonacci(4)}`)

.as-console-wrapper {min-height: 100% !important; top: 0}

Answer 2

You could take a different approach and visualize the side of the recursion by adding angle brackets as step and get the order of the calling with a side.

for example the recurion goes first all to the left side of bifurcation and then at the last step to the right side.

function fibonacci(n, step = { s: 0 }, sides = '') {
    console.log(++step.s, n, sides);
    if (n <= 1) return 1;
    return fibonacci(n - 1, step, sides + '< ') + fibonacci(n - 2, step, sides + '> ');
}

console.log(fibonacci(5));

.as-console-wrapper { max-height: 100% !important; top: 0; }