Recursive Approach & Tail Recursion

devfish·2023년 2월 13일
0

Javascript

목록 보기
25/30
post-thumbnail

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

https://javascript.plainenglish.io/js-recursion-and-tail-call-optimization-with-pictures-cbf8f766a31

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:

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

https://otee.dev/2022/04/03/understanding-tail-recursion.html

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

profile
la, di, lah

0개의 댓글