 Solution

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.