Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

54 FUNCTIONS AND ALGORITHMS [CHAP. 3

Level Numbers

LetPbe a procedure or recursive formula which is used to evaluatef(X)wherefis a recursive function
andXis the input. We associate alevel numberwith each execution ofPas follows. The original execution ofP
is assigned level 1; and each timePis executed because of a recursive call, its level is one more than the level
of the execution that made the recursive call. Thedepthof recursion in evaluatingf(X)refers to the maximum
level number ofPduring its execution.
Consider, for example, the evaluation of 4! Example 3.8, which uses the recursive formulan!=n(n− 1 )!.
Step 1 belongs to level 1 since it is the first execution of the formula. Thus:

Step 2 belongs to level 2; Step 3 to level 3,...; Step 5 to level 5.

On the other hand, Step 6 belongs to level 4 since it is the result of a return from level 5. In other words, Step 6

and Step 4 belong to the same level of execution. Similarly,

Step 7 belongs to level 3; Step 8 to level 2; and Step 9 to level 1.

Accordingly, in evaluating 4!, the depth of the recursion is 5.

Fibonacci Sequence

The celebrated Fibonacci sequence (usually denoted byF 0 ,F 1 ,F 2 ,...) is as follows:

0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , ...

That is,F 0 =0 andF 1 =1 and each succeeding term is the sum of the two preceding terms. For example, the
next two terms of the sequence are

34 + 55 =89 and 55+ 89 = 144

A formal definition of this function follows:

Definition 3.2 (Fibonacci Sequence):

(a) Ifn= 0 ,orn= 1 ,thenFn=n.

(b) Ifn> 1 ,thenFn=Fn− 2 +Fn− 1.

This is another example of a recursive definition, since the definition refers to itself when it usesFn− 2 and
Fn− 1 However:

(1) The base values are 0 and 1.

(2) The value ofFnis defined in terms of smaller values ofnwhich are closer to the base values.

Accordingly, this function is well-defined.

Ackermann Function

The Ackermann function is a function with two arguments, each of which can be assigned any nonnegative
interger, that is, 0, 1 , 2 ,.... This function is defined as:

Definition 3.3 (Ackermann function):

(a) Ifm= 0 ,thenA(m, n)=n+ 1.

(b) Ifm=0 butn= 0 ,thenA(m, n)=A(m− 1 , 1 ).

(c) Ifm=0 andn= 0 ,thenA(m, n)=A(m− 1 , A(m, n− 1 )).

Once more, we have a recursive definition, since the definition refers to itself in parts (b) and (c). Observe

thatA(m, n)is explicitly given only whenm=0. The base criteria are the pairs

( 0 , 0 ), ( 0 , 1 ), ( 0 , 2 ), ( 0 , 3 ), ...,( 0 ,n), ...