Iteration: a special case of Recursion

void do_loop () { do { ... } while (e); }

is equivalent to

void do_loop () { ...; if (e) do_loop(); }

A compiler can recognize instances of this form of recursion and turn them into loops or simple jumps:

void do_loop () { start: ...; if (e) goto start; }

Tail Calls

A call is a tail call if it is the last thing that needs to be executed in a particular invocation of the function where it occurs:

void zig (int n) { ...; if (e) zag(n-1); }

Before a tail call, the activation record of the caller can be discarded: the local space allocated to zig is released before calling zag.

Thus tail recursive algorithms (i.e. where all the recursive steps are tail calls) can be automatically optimized to execute in constant space.