= Solution
Replace the recursive transfer in part (b) by simultaneous state updates, using a temporary variable to preserve the old `a`:
``
PROCEDURE FibIter(n: INTEGER): INTEGER;
VAR k, a, b, oldA: INTEGER;
BEGIN
k := n; a := 1; b := 0;
WHILE k > 1 DO
oldA := a;
a := a + b;
b := oldA;
k := k - 1
END;
RETURN a
END FibIter;
``
For original input $N\geq1$, a <loop invariant> is
$$
\boxed{1\leq k\leq N,\qquad aF_k+bF_{k-1}=F_N.}
$$
It holds initially because $a=1,b=0,k=N$. Each iteration preserves it by the identity from part (b). The <loop variant> is $k-1$, a nonnegative <integer> that decreases by one whenever the guard holds. On exit $k=1$, so the <loop invariant> gives $aF_1+bF_0=a=F_N$, exactly the returned answer. The procedure uses $O(n)$ arithmetic operations and $O(1)$ stored <integer> variables, without depending on compiler treatment of <tail calls>.
Back to article page
