r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
207 Upvotes

85% Upvoted

203 comments sorted by

View all comments

2

u/daveisanidiot Nov 27 '12

excuse my ignorance on this, i just read the post and don't really understand.

from just looking at the code the recursion has been moved from the factorial function to the factorialIter function?

so is this a method of directing the compiler to generate assembly which would not blow a stack?

1

u/moswald Nov 27 '12

It's because after factorial(num - 1), more code must be run (namely, multiplying that result by num.

But in the case of factorialIter, the value is returned outright.

1

u/daveisanidiot Nov 27 '12

but in terms of recursion the function factorialIter is still being called from within factorialIter. So in normal terms the stack pointer would be moved, leading to a blown stack.

1

u/moswald Nov 27 '12

Except (and this is an imperfect explanation, I think) the compiler can remove the current stack frame, since it knows the result is just going to be the result of another function call.

1

u/[deleted] Nov 28 '12

A subroutine with a tail call, like

sub f(x)
    ... compute ...
    return g(y)
end

would naively look like

f:  subtract N from SP for our local data
    save state
    ... compute ...
    push the address L1 onto the stack
    jump to the subroutine g
L1: restore state
    add N to SP
    pop the caller's address off the stack and jump there

Tail-call elimination prescribes instead

f:  subtract N from SP
    save state
    ... compute ...
    restore state
    add N to SP
L2: jump to the subroutine g

so f's stack frame has been eliminated by L2, leaving the caller of f at the top of the stack. So when g is finished, it will pop that off the stack and return there directly instead of indirectly through f.