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

An Oberon recursive procedure can implement the defining recurrence relation directly. Its precondition is

n \geq 1

; arithmetic is assumed to remain in the representable integer range.

PROCEDURE Fib(n: INTEGER): INTEGER;
  VAR result: INTEGER;
BEGIN
  IF n <= 2 THEN
    result := 1
  ELSE
    result := Fib(n-1) + Fib(n-2)
  END;
  RETURN result
END Fib;

Correctness follows by strong induction: the two base inputs give

1

, and for

n > 2

the returned sum is

F_{n - 1} + F_{n - 2} = F_{n}

. On each recursive branch the positive integer argument strictly decreases, while recursion stops at

1

2

. The well-ordering principle therefore proves algorithm termination.

Fib (n) = F_{n} (n \geq 1) .

(1)

The method repeats many subproblems and has exponential time complexity; termination alone does not make it efficient.

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

a F_{n} + b F_{n - 1} = (a + b) F_{n - 1} + a F_{n - 2} = g (n - 1, a + b, a),

(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. Thus

F_{n} = g (n, 1, 0), g (n, a, b) = g (n - 1, a + b, a) (n > 1) .

(2)

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.

c

 0  0

Solution

 0  0

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