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