Section 3.3 Analysis of Algorithms
207
EXAMPLE 29
We can recast the sequential search algorithm from an iterative version
(repeating some action over and over in a loop) to a recursive version. The base
case says that you check whether you have run off the end of the list and if not,
you check for the target x at the first position in the list. If you find it, fine, if not,
then you invoke the algorithm again on the rest of the list. Here is pseudocode
for the recursive function to search the list from L[i] to L[n]; the function is
invoked initially with i = 1.
ALgorithM SequentialSearchrecurSive
SequentialSearchRecursive(list L; integer i, n; itemtype x)
//searches list L from L[i] to L[n] for item x
if i > n then
write(“not found”)
else
if L[i] = x then
write(“found”)
else
SequentialSearchRecursive(L, i + 1, n, x)
end if
end if
end function SequentialSearchRecursive
Figure 3.3 gives a visual representation of the recursive sequential search algorithm.
Each time the algorithm is invoked, the new list to be searched is only 1 element shorter
than the previous list, so in the worst case the algorithm has to work quite hard.
Search
here;
if fail,
not in list
Search
here;
if fail,
search here
Search
here;
if fail,
search here
if fail,
search here
Search
here;
Search
here;
Search
here;
if fail,
search here
if fail,
search here
Figure 3.3