(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)

**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.

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

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.

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*).

**Question**

Give a variant function for

**Algorithm** fibonacci(*n*):

*Input:* integer

*Output:* *n*th 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)