Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / e

A directly self-recursive procedure can be replaced by a simple loop when every recursive call is a tail call. This is tail recursion: no operation, including an update or cleanup action, remains to be performed after the call returns. The loop tests the same cases, performs the same nonrecursive work, and replaces the current parameters by the next call's arguments. Argument values must be computed before assignments if their expressions depend on old parameter values; by-reference bindings also need preserving.

A traversal that must return to explore another child is not in this form. It can still be implemented iteratively with an explicit stack, but that is a different transformation and generally retains the deferred work.