Recursion
Two characteristics:
- base case that stops recursion
- calling itself
Says that recursion "works great" in theory where you have unlimited memory and unlimited CPU.
The primary problem is memory.
Stack frame, the first time the function is called. When it's done it's thrown away. Each function call takes up a stack frame.
Normally you only have 10-15 deep call stack. In old IE there was a limit of 13 stack frames. In more modern browser there's still a limit even if it's much higher.
On modern phones, the phone shuts off if it runs out of memory.
With recursion it's very easy to grow your stack too high.
The main advantage of recursion is expressivity. Easy to express gracefully complex problems.
Loops (iteration) and recursion are isomorphic. Many compilers (not JS) "unroll" recursions to loops.
In ES6 we can reclaim recursion. In ES6 it's required to optimise for recursion. Normally it's a technical detail left to engine creators.In ES6 it is required. TCO, Tail-call-optimisation. or Proper tail calls.
Proper tail call is when a function's very last statement is to return a call to another function:
function funcA() {
..
return funcB(..);
}
In this case the JavaScript engine can optimise and use the same stack frame for funcB. So if all recursion calls are done this way we have "constant memory usage". One stack frame reuse.