March 9, 2001

Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(1st) pages 162-163 (Section 5.3.1), pages 152-161 (Section 5.2.1-5.2.3), pages 165-172 (Section 5.3.3)

(2nd) pages 249-250 (Section 6.3.3), pages 236-246 (Section 6.2.1-6.2.4), pages 251-257 (Section 6.3.4)

Additional material

Proof of Proposition 5.9 and 5.10/Proposition 6.10 and 6.11 in PostScript and PDF.

Variant function

Before we can reason inductively about recursive algorithms, we need to prove that the algorithm terminates. To show that there is no infinite recursion without tracing through the actual computation, we introduce a variant function. This function maps each instance of the parameters satisfying the precondition to a natural number. That is, it is a function from instances to natural numbers. Consider for example

Algorithm factorial(n):
   Input: integer
   Output: n!
   Precondition: n > 0
if n = 1 then
     return 1
else
     return n * factorial(n - 1)

The variant function variant has to map each instance of the parameters satisfying the precondition, in this example a positive integer, to a natural number. This natural number can be thought of as an upperbound of the number of recursive calls this instance gives rise to. For example, factorial(n) gives rise to n - 1 recursive calls.

To prove that a recursive algorithm does not lead to infinite recursion, it is enough to find a variant function variant with the following two properties:

variant maps instances of the base case(s) to 0.
variant maps (the instances of) recursive calls to a smaller number than (the instance of) original call.

For example, for factorial the above properties amount to:

variant(1) = 0.
variant(n - 1) < variant(n).

The function variant(n) = n - 1 satisfies the above two properties. Note that the variant function is not unique. For example, the variant function defined by variant(n) = 2n - 2 also satisfies the above properties.

Let us have a look at another example. Consider the following algorithm.

Algorithm numberOfNodes(node):
   Input: node of a binary tree
   Output: number of nodes of the subtree rooted at node
if node is a leaf then
     return 1
else
     return numberOfNodes(left child of node) + numberOfNodes(right child of node) + 1

In this example, the instances of the parameters are nodes of a binary tree. The variant function variant has to satisfy

variant(node) = 0 if node is a leaf and
variant(left child of node) < variant(node) and variant(right child of node) < variant(node) if node is not a leaf.

Consider the function variant(node) = number of internal nodes of the subtree rooted at node. One can easily check that it satisfies the above properties, and hence prove that the recursive algorithm eventually terminates.

Now consider the following algorithm.

Algorithm f(n):
   Input: integer
   Output: 1
   Precondition: n > 0
if n = 1 then
     return 1
else
     return f(n + 1)

Again the instances are positive integers. In this case, the variant function variant should satisfy

variant(1) = 0.
variant(n + 1) < variant(n).

We cannot find such a function. This is not surprising. The algorithm does not terminate for any integer greater than 1.

Question

Give a variant function for

Algorithm fibonacci(n):
   Input: integer
   Output: nth Fibonacci number
   Precondition: n >= 0
if n = 0 then
     return 1
else if n = 1 then
     return 1
else
     return fibonacci(n - 1) + fibonacci(n - 2)