are used but the stack size is checked before every call. When the stack reaches its maximum permitted size, objects on the stack are garbage-collected using the Cheney algorithm by moving all live data into a separate heap. Following this, the stack is unwound ("popped") and the program resumes from the state saved just before the garbage collection. Baker says "Appel's method avoids making a large number of small trampoline bounces by occasionally jumping off the Empire State Building." The garbage collection ensures that mutual tail recursion can continue indefinitely. However, this approach requires that no C function call ever returns, since there is no guarantee that its caller's stack frame still exists; therefore, it involves a much more dramatic internal rewriting of the program code: continuation-passing style. Relation to the while statement Tail recursion can be related to the while statement, an explicit iteration, for instance by transforming procedure foo(x) if p(x) return bar(x) else return foo(baz(x)) into procedure foo(x) while true if p(x) return bar(x) else x ← baz(x) where x may be a tuple involving more than one variable: if so, care must be taken in implementing the assignment statement x ← baz(x) so that dependencies are respected. One may need to introduce auxiliary variables or use a swap construct. More generally, procedure foo(x) if p(x) return bar(x) else if q(x) return baz(x) ... else if r(x) return foo(qux(x)) ... else return foo(quux(x)) can be transformed into procedure foo(x) while true if p(x) return bar(x) else if q(x) return baz(x) ... else if r(x) x ← qux(x) ... else x ← quux(x) For instance, this Python program gives a non-tail recursive definition fact of the factorial: def fact(n): if n == 0: return 1 else: return n * fact(n - 1) Indeed, n * fact(n - 1) wraps the call to fact. But it can be transformed into a tail-recursive definition by adding an argument a called an accumulator. This Python program gives a tail-recursive definition fact_iter of the factorial: def fact_iter(n, a): if n == 0: return a else: return fact_iter(n - 1, n * a) def fact(n): return fact_iter(n, 1) This Python program gives an iterative definition fact_iter of the factorial: def fact_iter(n, a): while True: if n == 0: return a else: n, a = n - 1, n * a def fact(n): return fact_iter(n, 1) Language support Clojure Clojure has recur special form.