86.md

Solution

Submission link - https://bigfrontend.dev/problem/fibonacci-number/discuss/260

This also covers - 93. Generate Fibonacci Number with recursion

/**
 * @param {number} n - non-negative integer
 * @return {number}
 */
function fib(n, acc1 = 0, acc2 = 1) {
  console.count();
  if (n == 0) return 0;

  if (n == 1) {
    if (acc2 == 1) return 1;
    return acc2;
  }

  return fib(n - 1, acc2, acc1 + acc2);
}

Short story

I have solved the problem with recursion but without tail call optimization (TCO).
The solution was acceptable but it was calling fib(8) 67 times.

I started looking for other posted solutions and found that a user EzrealPrince has posted
a better solution. I checked console.count() and it was 8 times fib(8).

This has taught me that when you want to reduce Space complexity or want to have proper TCO then consider function parameters (with default values) to hold calculation for you. At least your function won't fill stack frames.

Algorithm -

1. Use two additional parameters with 2 initial numbers - 0 and 1 (because Fibonacci series is: 0, 1, 1, 2, 3, 5, 8...)
2. Add first terminator condition n === 0
3. Add another terminator condition n === 1.
4. If acc2 is 1 means fib(1)
5. else n is reduced by recursion till n = 1
6. Call fib recursively until it meets those terminator conditions

Time complexity*	Space complexity*
O(1)	O(1)

^* = I hope this is the correct Big O values for the solution.

Resources -

1. Original solution by EzrealPrince

---

Twitter: (@knowkalpesh)