166
Recursion, Recurrence Relations, and Analysis of Algorithms
Assume that for n = k and 1 ≤ p ≤ k − 1,
(A 1 ~ c~ A p ) ~ (A p+1 ~ c~ A k ) 3 A 1 ~ c~ A k
Then for n = k + 1 and 1 ≤ p ≤ k,
(A 1 ~ c~ A p ) ~ (A p+1 ~ c~ A k+1 )
= (A 1 ~ c~ A p ) ~ 3(A p+1 ~ c~ A k ) ~ A k+1 4
(by equation (2))
3 3(A 1 ~ c~ A p ) ~ (A p+1 ~ c~ A K ) 4 ~ A k+1
(by equivalence 2a)
3 (A 1 ~ c~ A k ) ~ A k+1
(by inductive hypothesis)
= A 1 ~ c~ A k+1
(by equation (2))
Recursively Defined Algorithms
Example 1 gives a recursive definition for a sequence S. Suppose we want to
write a computer program to evaluate S(n) for some positive integer n. We can use
either of two approaches. If we want to find S(12), for example, we can begin with
S(1) = 2 and then compute S(2), S(3), and so on, much as we did in Example 1,
until we finally get to S(12). This approach no doubt involves iterating through
some sort of loop. A pseudocode function S that uses this iterative algorithm
follows. The basis, where n = 1, is handled in the first clause of the if statement;
the value 2 is returned. The else clause, for n > 1, does some initializing and then
goes into the while loop that computes larger values of the sequence until the
correct upper limit is reached. You can trace the execution of this algorithm for a
few values of n to convince yourself that it works.
algorIthm
S(positive integer n)
//function that iteratively computes the value S(n)
//for the sequence S of Example 1
Local variables:
integer i
//loop index
CurrentValue //current value of function S
if n = 1 then
return 2
else
i = 2
CurrentValue = 2
while i <= n do
CurrentValue = 2 * CurrentValue
i = i + 1
end while
//CurrentValue now has the value S(n)
return CurrentValue
end if
end function S