Calculate n-th Fibonacci number using Tail Recursion

In traditional recursion, you perform the recursive call, take the return value of that call and calculate the results. You get the results of your calculation only until you’ve returned from every recursive call, requiring a lot of space on the call stack:

function fib(n){
  if (n === 1) return 0;
  if (n === 2) return 1; 
  return fib(n — 1) + fib(n — 2);
}

In tail recursion, you calculate the results first, and pass the results of your current call onto the next recursive call:

function fib(n, a = 0, b = 1){
  if (n > 0) {
    return fib(n - 1, b, a + b)
  }
  return a
}

Now, when you are ready to calculate the next call, you don’t need the current stack frame. You are calculating the results and passing them as parameters to your next call. No more worries about stack overflow! This tail recursive solution is constant O(n) time and constant O(n) space complexity.