JavaScript will only optimize into a non-recursive loop a recursive step if it is the last expression in a block (IIUC). Does that mean that the right-hand recursive call will be optimised and the left-hand recursive call will NOT in the following?
function fibonacci(n) {
if(n < 2) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
Does that mean that the right-hand recursive call will be optimised and the left-hand recursive call will NOT in the following?
I don't think so. TCO is only possible when you directly return what other function returns. Since your function processes both results before returning them, neither of the calls can be tail-optimized.
In terms of a stack-based machine, a code like this:
function fun1()
return fun2(42)
function fun2(arg)
return arg + 1
is translated to this
fun1:
push 42
call fun2
result = pop
push result
exit
fun2:
arg = pop
arg = arg + 1
push arg
exit
TCO can eliminate call-pop-push and instead jump to fun2 directly:
fun1:
push 42
goto fun2
exit
However, a snippet like yours would be this:
fun1:
push n - 1
call fun2
result1 = pop
push n - 2
call fun2
result2 = pop
result3 = result1 + result2
push result3
exit
Here, it's not possible to replace calls with jumps, because we need to return back to fun1 to perform the addition.
Disclaimer: this is a rather theoretical explanation, I have no idea how modern JS compilers actually implement TCO. They are quite smart, so perhaps there's a way to optimize stuff like this as well.
fun1: "create a stack frame for the call to fun2 with 42 as an argument, capture the result in the calling stack frame as the return value for the frame and pop the frame"? Any exposition on why the jump optimisation is valid would be very helpful too.
fibonacci(n-1)is almost always going to callfibonacci(n-2)as part of its own recursion, so you could optimise that. Or you could have aknown_fiblist that is checked first, and only if a number is not in the list doesfibonacci()calculate it. (the latter will reducefibonacci(n-2)to a single lookup)