Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 6 / c

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\ge 1$, a loop invariant isIt 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 $a{F}_1+b{F}_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.