= 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)=aF_n+bF_{n-1}$. For $n>1$,
$$
aF_n+bF_{n-1}=(a+b)F_{n-1}+aF_{n-2}
=g(n-1,a+b,a),
$$
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>. Thus
$$
\boxed{F_n=g(n,1,0),\qquad g(n,a,b)=g(n-1,a+b,a)\ (n>1).}
$$
There 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.
Back to article page
