168
Recursion, Recurrence Relations, and Analysis of Algorithms
A recursive algorithm invokes itself with “smaller” input values. Suppose a
problem can be solved by solving smaller versions of the same problem, and the
smaller versions eventually become trivial cases that are easily handled. Then
a recursive algorithm can be useful, even if the original problem was not stated
recursively.
To convince ourselves that a given recursive algorithm works, we don’t have to
start with a particular input and go down through smaller and smaller cases to the
trivial case and then back up again. We did this when discussing the computation
of S(3), but that was just to illustrate the mechanics of a recursive computation.
Instead, we can verify the trivial case (like proving the base case in an induction
proof) and verify that if the algorithm works correctly when invoked on smaller
input values, then it indeed solves the problem for the original input values (this
is similar to proving P(k + 1) from the assumption P(k) in an inductive proof).
■
PRaCtiCe 9 Write the body of a recursive function to compute T(n) for the sequence T defined in
Practice 1.
example 11
In Example 10, a recursive definition was given for multiplying two positive
integers m and n. A recursive pseudocode function for multiplication based on this
definition follows.
algorIthm
Product(positive integer m; positive integer n)
//Function that recursively computes the product of m and n
if n = 1 then
return m;
else
return Product(m, n − 1) + m
end if
end function Product
remInDer
Think of a recursive
algorithm whenever you
could solve the problem
from solutions to smaller
versions of the problem.
example 12
One of the most common tasks in data processing is to sort a list L of n items into
increasing or decreasing numerical or alphabetical order. (The list might consist of
customer names, for example, and in sorted order “Valdez, Juanita” should come
after “Tucker, Joseph.”) The selection sort algorithm—a simple but not particularly
efficient sorting algorithm—is described in pseudocode in the accompanying box.
This function sorts the first j items in L into increasing order; when the function is initially invoked, j has the value n (thus, the first invocation ultimately sorts
the entire list). The recursive part of the algorithm lies within the else clause; the
algorithm examines the section of the list under consideration and finds the location i such that L[i] is the maximum value. It then exchanges L[i] and L[ j], after
which the maximum value occurs at position j, the last position in the part of the
list being considered. L[ j] is now correct and should never change again, so this
Recursion, Recurrence Relations, and Analysis of Algorithms
A recursive algorithm invokes itself with “smaller” input values. Suppose a
problem can be solved by solving smaller versions of the same problem, and the
smaller versions eventually become trivial cases that are easily handled. Then
a recursive algorithm can be useful, even if the original problem was not stated
recursively.
To convince ourselves that a given recursive algorithm works, we don’t have to
start with a particular input and go down through smaller and smaller cases to the
trivial case and then back up again. We did this when discussing the computation
of S(3), but that was just to illustrate the mechanics of a recursive computation.
Instead, we can verify the trivial case (like proving the base case in an induction
proof) and verify that if the algorithm works correctly when invoked on smaller
input values, then it indeed solves the problem for the original input values (this
is similar to proving P(k + 1) from the assumption P(k) in an inductive proof).
■
PRaCtiCe 9 Write the body of a recursive function to compute T(n) for the sequence T defined in
Practice 1.
example 11
In Example 10, a recursive definition was given for multiplying two positive
integers m and n. A recursive pseudocode function for multiplication based on this
definition follows.
algorIthm
Product(positive integer m; positive integer n)
//Function that recursively computes the product of m and n
if n = 1 then
return m;
else
return Product(m, n − 1) + m
end if
end function Product
remInDer
Think of a recursive
algorithm whenever you
could solve the problem
from solutions to smaller
versions of the problem.
example 12
One of the most common tasks in data processing is to sort a list L of n items into
increasing or decreasing numerical or alphabetical order. (The list might consist of
customer names, for example, and in sorted order “Valdez, Juanita” should come
after “Tucker, Joseph.”) The selection sort algorithm—a simple but not particularly
efficient sorting algorithm—is described in pseudocode in the accompanying box.
This function sorts the first j items in L into increasing order; when the function is initially invoked, j has the value n (thus, the first invocation ultimately sorts
the entire list). The recursive part of the algorithm lies within the else clause; the
algorithm examines the section of the list under consideration and finds the location i such that L[i] is the maximum value. It then exchanges L[i] and L[ j], after
which the maximum value occurs at position j, the last position in the part of the
list being considered. L[ j] is now correct and should never change again, so this