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

*result* 1

**else**

*result* *n* * factorial(*n* - 1)

**return** *result*

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

*result* 1

**else**

*result* 1+ numberOfNodes(left child of *node*) +
numberOfNodes(right child of *node*)

**return** *result*

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

*result* 1

**else**

*result* f(*n* + 1)

**return** *result*

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

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

**Binary search trees**

The definition of a binary search tree can be found on page 382 of the textbook (this definition may be different from one used in 1030). Next, we discuss three recursive algorithms that test if a given binary tree whose nodes contains keys is a binary search tree.

**Algorithm** isBST(*tree*):

*Input:* a binary tree whose nodes contains keys

*Output:* *tree* is a binary search tree?

**if** *tree* has one node **then**

*result* true

**else**

*result*
isBST(left subtree of *tree*)
isBST(right subtree of *tree*)
areLessThanOrEqual(*key*, left subtree of *tree*)
areGreaterThanOrEqual(*key*, right subtree of *tree*)

**return** *result*

**Algorithm** areLessThanOrEqual(*key*, *tree*):

*Input:* key and a binary tree whose nodes contains keys

*Output:* for all nodes *node* : *node* is node of *tree* : key of *node* <= *key*?

**if** *tree* has one node **then**

*result* key of root of *tree* <= *key*

**else**

*result* key of root of *tree* <= *key*
areLessThanOrEqual(*key*, left subtree of *tree*)
areLessThanOrEqual(*key*, right subtree of *tree*)

**return** *result*

The recursive algorithm areGreaterThanOrEqual can be defined similarly (left
as an easy exercise). The worst-case running time of isBST(*tree*) is
*O*(*n*^{2}), where *n* is the number of nodes of
*tree*. The worst-case running time of the next algorithm is
*O*(*n*).

**Algorithm** isBST(*tree*):

*Input:* a binary tree whose nodes contains keys

*Output:* (*tree* is a binary search tree?,
minimal key stored in *tree*, maximal key stored in *tree*)

**if** *tree* has one node **then**

*result* (true, key of root of *tree*, key of root of *tree*)

**else**

(*isBST*_{left}, *min*_{left}, *max*_{left})
isBST(left subtree of *tree*)

(*isBST*_{right}, *min*_{right}, *max*_{right})
isBST(right subtree of *tree*)

*isBST*
*isBST*_{left} *isBST*_{right}
*max*_{left} <= key of root of *tree* <= *min*_{right}

*min* min(key of root of *tree*, *min*_{left}, *min*_{right})

*max* min(key of root of *tree*, *max*_{left}, *max*_{right})

*result* (*isBST*, *min*, *max*)

**return** *result*

Complete the following algorithm.

**Algorithm** isBST(*tree*, *min*, *max*):

*Input:* a binary tree whose nodes contains keys and a minimal and maximal key

*Output:* *tree* is a binary search tree?
for all *node* : *node* is a node of *tree* : *min* <= key of *node* <= *max*?

Which values should one take for *min* and *max* to check if
*tree* is a binary search tree?