Recursive Approach & Tail Recursion

Recursive Approach: A Template

A recursive algorithm can be defined as solving a problem by solving a smaller version of the same problem (a sub-problem) and then using that solution to solve the original problem. To solve a sub-problem, we need to solve a still smaller version of that sub-problem and so on. To prevent an infinite series of sub-problems, we need the series of sub-problems to eventually terminate at a base case. ~link

Recursive functions: Best Use Scenarios

Iterative methods (loops) are way more efficient in general, but there are occasions that merit the use of recursion as follows:

• ... solving problems that can be broken down into smaller, repetitive problems. It is especially good for working on things that have many possible branches and are too complex for an iterative approach
• When there are too many nested loops, or the number of loops is difficult to predict

In the above cases, using recursion makes cleaner, more readable code.

Tail Recursion

ECMAScript 6 offers tail call optimization, where you can make some function calls without growing the call stack. [...] Roughly, whenever the last thing a function does is to call another function then the latter does not need to return to its caller. As a consequence, no information needs to be stored on the call stack and the function call is more of a goto (a jump). This kind of call is named tail call; not growing the stack is named tail call optimization (TCO). ~link

Classic(non-tail) vs. tail recursion examples

Exemplified in Factorial (n!):

//non-tail recursion 
function factorial(n){
    if(n <= 1)//.... (1)
        return 1
    return n * factorial(n - 1)// ... (2)
}

//tail recursion 
function factorial(n, acc = 1){
  if (n <= 1) return acc;
  return factorial(n-1, acc*n); 
}

Call Stack & Stack Overflow

How the call stack works for recursive functions (click here for detailed step-by-step explanations)

... and so on.

Without TCO (4 stack frames):

With TCO (1 stack frame):

Tail Recursion Optimization (TCO) in JS

As of now, TCO is only supported in the Safari browser. Chrome V8 and Node.js briefly supported TCO for a hot second until it was dropped completely. In ES6, however, TCO can be utilized in 'strict' mode. (Need to confirm) The idea behind it is still interesting and worth noting (as well as widely practiced in other languages.)

The primary reason it was kicked out was the lack of debugging support. Calling functions are in the source code but not in the stack anymore, leading to confusion since it looks like the function gets called only once. Making even more problems during error hunting and debugging at all. ~link

By utilizing console.trace(), you can see that chrome's lack of support for TCO

This is what's happening under the hood:

// sum(number, acc = 0)
call sum(4, 0)
  call sum(3, 4)
    call sum(2, 7)
      call sum(1, 9)
        return 10
      return 10
    return 10
  return 10

Whereas Safari does!

//sum(number, acc = 0)
call sum(4, 0)
replace with sum(3, 4)
replace with sum(2, 7)
replace with sum(1, 9)
return 10

Trampolining (For Further Study)

A way to simulate TCO in an iterative way, which is ideal for controlling function stack growth.

References

• JavaScript: Recursion, Tail-Call Optimization and Trampolining with Pictures
  (many imgs were lifted from link!)
• When to Loop, When to Recurse
• Understanding Tail Recursion (4.2022)
• ES6: Tail Call Optimization
• Tail Calls in Javascript: Will There Be a Comeback? (12.2020)
• ES6 Tail Recursion Optimisation Stack Overflow
• 꼬리 재귀 함수란?