Discrete Mathematics for Computer Science

224 CHAPTER 4 Functions

4.1.3 Recursively Defined Functions

When a function F is defined by a formula, we can find the value of F at any element

of its domain without knowing its value at any other element of its domain. For example,

consider the function F : N -* N defined by the rule F(n) = 3n + 2. We can compute

directly that F(100) = 3. 100 + 2 = (^302) or that F(3112) = 3.3112 + 2 = 9338.
Functions, however, are not necessarily defined in such a straightforward manner. Con-
sider the function G : N -- N defined as G(0) = 2 and, for n > 0, G(n) = G(n - 1) + 3.

Then, G(1) = G(0) + 3 = 2 + 3 = 5. The following computation shows how G(5) would

be determined:

G(5) = G(4) + 3

= G(3) +3+3

= G(2)+3+3+3

= G(1)+3+3+3+3

= G(0)+3+3+3+3+3

= 2+3.5

17

If we now wanted G(3112), we would first need to compute G(1), G(2),..., G(3111). In

this situation, we say that G is defined recursively or is given by a recursive definition.

As you might suspect from the computation of G(5), the two functions F and G are

actually the same; that is, F(n) = G(n) for every n E N. In Section 1.10.1, F was described

as a closed form for G.

Example 11.

(a) The function F : N - N defined as F(n) = 3f can be defined recursively as F(0) = 1

and F(n) = 3. F(n - 1) for n > 1.

(b) The sum of the first k of n elements al, a2. an can be defined directly as SUM(k) =

al + a2 + • • ± + ak where 1 < k < n. Recursively, the same function can be defined as

S(1) = al and S(k) = S(k- 1)+ak fork > 1.

(c) The sum of the first n terms of a geometric series a + ac + ac^2 + ac

(^3) + • .+ acn-I
can be defined as gs(0) = a and gs(k) = gs(k - 1) + ack for k > 1.

(d) The harmonic sequence that consists of the terms 1, 1/2, 1/3 .... 1/n, ... can have

the sum of its first k terms defined as the function H(1) = 1 and H(k) = H(k - 1) +

l/kfork > 1.

We introduced the Fibonacci sequence in Section 1.7.3. This sequence of values

(1, 1, 2, 3, 5, 8, 13 .... ) was defined recursively; that is, no direct formula was given for

finding the nth element of the Fibonacci sequence. Unlike the functions in Example 8, two

terms are given as initial conditions for termination conditions in defining the nth element

of the Fibonacci sequence successively in terms of smaller Fibonacci numbers. The defini-

tion of the Fibonacci sequence is F(0) = 1, F(1) = 1, and F(n) = F(n - 1) + F(n - 2)

for n > 2. The first five terms of the Fibonacci sequence are found as follows: