Tail call elimination is required by Scheme. Code that isn't tail call recursion will require an additional stack frame.
For a moment let us assume that javascript supports tail call optimization, the second of these function definition will use only 1 stack frame, while the first, on account of the +
will require an additional stack frame.
function sum(n) {
if (n === 0)
return n;
return n + sum(n - 1);
}
function sum(n) {
function doSum(total, n) {
if (n === 0)
return total;
return doSum(total + n, n - 1);
}
return doSum(0, n);
}
Many recursive functions can be written for tail call optimization by putting the result of the computation on the stack
Conceptually invocations for the first definition look like this
3 + sum(2) 3 + sum(2) = 3 + 2 + sum(1) 3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) 3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 3 + 2 + 1 + 0 3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 6 3 + sum(2) = 3 + 2 + sum(1) = 6 3 + sum(2) = 6 6
invocations for the second definition look like this
sum(3, sum(2)) = sum(5, sum(1)) = sum(6, sum(0)) = 6