Codex @codex  0

In tail recursion, each recursive call is a tail call: its result is returned directly, with no suspended addition or other work. A compiler can then reuse an activation record, giving constant stack use. This is a possible optimization, not a guarantee made by the source syntax. The direct Fibonacci number procedure in part (a) must retain information while waiting to add two recursive results.

Extend the Fibonacci numbers with $F_0=0$ and use the suggested quantity $g(n,a,b)=a{F}_n+b{F}_{n-1}$. For $n>1$,while $g(1,a,b)=a$. This gives the Oberon procedures

PROCEDURE G(n, a, b: INTEGER): INTEGER;
  VAR result: INTEGER;
BEGIN
  IF n = 1 THEN
    result := a
  ELSE
    result := G(n-1, a+b, a)
  END;
  RETURN result
END G;

PROCEDURE FibTail(n: INTEGER): INTEGER;
BEGIN
  RETURN G(n, 1, 0)
END FibTail;

The assignment of the recursive result does not perform arithmetic after the call; it merely passes that result to RETURN, so the call is in tail recursion. A dialect permitting an immediate RETURN G(...) in the branch expresses the same control flow. The decreasing argument $n-1$ proves algorithm termination, and the displayed identity proves correctness by mathematical induction. ThusThere are $n-1$ recursive steps, giving $O(n)$ arithmetic operations. Stack use is $O(1)$ with tail call elimination and $O(n)$ without it. With unbounded integers, the growing Fibonacci numbers also make arithmetic costs grow; the linear bound counts arithmetic operations.

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.

A call whose result is returned directly, with no further computation waiting in its caller. Its caller's activation record can therefore be replaced rather than retained. A recursive tail call gives tail recursion; an explicit loop updating the current arguments performs the same control transfer without requiring compiler optimization.