CODEWITHSUNDEEP
recursiontail-recursion
Nathan Long
Nathan Long

Reputation: 125892

Can tail recursion support shorten the stack for other function calls?

Can languages that support tail recursion apply the same technique to non-recursive function calls?

For example, if the last thing that function foo does is return the value of calling bar, might the language discard foo's stack frame? Are any languages known to actually do this?

Upvotes: 3

Views: 89

Answers (2)

Jakub M.
Jakub M.

Reputation: 33817

Erlang does:

Tail recursion as seen here is not making the memory grow because when the virtual machine sees a function calling itself in a tail position (the last expression to be evaluated in a function), it eliminates the current stack frame. This is called tail-call optimisation (TCO) and it is a special case of a more general optimisation named Last Call Optimisation (LCO).

LCO is done whenever the last expression to be evaluated in a function body is another function call. When that happens, as with TCO, the Erlang VM avoids storing the stack frame. As such tail recursion is also possible between multiple functions. As an example, the chain of functions a() -> b(). b() -> c(). c() -> a(). will effectively create an infinite loop that won't go out of memory as LCO avoids overflowing the stack. This principle, combined with our use of accumulators is what makes tail recursion useful.

Upvotes: 2

NPE
NPE

Reputation: 500167

Yes it can. For example, consider the following C code:

int f();
int g() { return f(); }

When I compile this using gcc 4.6.3 with -O3 on x86-64, I get the following assembly for g():

g:
        xorl    %eax, %eax
        jmp     f              ; <==== unconditional jump to f

Upvotes: 1

Related Questions