CODEWITHSUNDEEP
javascriptrecursion
Ben Aston
Ben Aston

Reputation: 55729

Tail recursion optimization in JavaScript

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);
}

Upvotes: 4

Views: 180

Answers (1)

georg
georg

Reputation: 214949

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.

Low-level explanation

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.

Upvotes: 3

Related Questions