Section 3.1 Recursive Definitions
167
The second approach to computing S(n) uses the recursive definition of S
directly. Following is a version of the recursive algorithm, written again as a
pseudocode function.
The body of this function consists of a single if-then-else statement. To understand how the function works, let’s trace the execution to compute the value
of S(3). The function is first invoked with an input value of n = 3. Because n is
not 1, execution is directed to the else clause. At this point, activity on computing
S(3) must be suspended until the value of S(2) is known. Any known information
relevant to the computation of S(3) is stored within computer memory on a stack,
to be retrieved when the computation can be completed. (A stack is a collection
of data where any new item goes on top of the stack, and only the item on top of
the stack at any given time can be accessed or removed from the stack. A stack is
thus a LIFO—last in, first out—structure.) The function is invoked again with an
input value of n = 2. Again, the else clause is executed, and computation of S(2)
is suspended, with relevant information stored on the stack, while the function is
invoked again with n = 1 as input.
This time the first clause of the if statement applies, and the functional value, 2,
can be computed directly. This final invocation of the function is now complete, and
its value of 2 is returned to the second-to-last invocation, which can now remove
any information relevant to the n = 2 case from the stack, compute S(2), and return
the result to the previous (initial) invocation. Finally, this original invocation of S
is able to empty the stack and complete its calculation, returning the value of S(3).
What are the relative advantages of iterative and recursive algorithms for doing
the same task? In this example, the recursive version is certainly shorter because it
does not have to manage a loop computation. Describing the execution of the recursive version makes it sound more complex than the iterative version, but all steps are
carried out automatically. One need not be aware of what is happening internally
except to note that a long series of recursive invocations can use a lot of memory
by storing information relevant to previous invocations on the stack. If too much
memory is consumed, a “stack overflow” can result. Besides using more memory,
recursive algorithms can require many more computations and can run more slowly
than nonrecursive ones (see Exercise 3 in On the Computer at the end of this chapter).
Nonetheless, recursion provides a natural way to think about many problems,
some of which would have very complex nonrecursive solutions. The problem of
computing values for a sequence that has itself been defined recursively is wellsuited to a recursive solution. Many programming languages support recursion.
algorIthm
S(positive integer n)
//function that recursively computes the value S(n)
//for the sequence S of Example 1
if n = 1 then
return 2
else
return 2 * S(n − 1)
end if
end function S
167
The second approach to computing S(n) uses the recursive definition of S
directly. Following is a version of the recursive algorithm, written again as a
pseudocode function.
The body of this function consists of a single if-then-else statement. To understand how the function works, let’s trace the execution to compute the value
of S(3). The function is first invoked with an input value of n = 3. Because n is
not 1, execution is directed to the else clause. At this point, activity on computing
S(3) must be suspended until the value of S(2) is known. Any known information
relevant to the computation of S(3) is stored within computer memory on a stack,
to be retrieved when the computation can be completed. (A stack is a collection
of data where any new item goes on top of the stack, and only the item on top of
the stack at any given time can be accessed or removed from the stack. A stack is
thus a LIFO—last in, first out—structure.) The function is invoked again with an
input value of n = 2. Again, the else clause is executed, and computation of S(2)
is suspended, with relevant information stored on the stack, while the function is
invoked again with n = 1 as input.
This time the first clause of the if statement applies, and the functional value, 2,
can be computed directly. This final invocation of the function is now complete, and
its value of 2 is returned to the second-to-last invocation, which can now remove
any information relevant to the n = 2 case from the stack, compute S(2), and return
the result to the previous (initial) invocation. Finally, this original invocation of S
is able to empty the stack and complete its calculation, returning the value of S(3).
What are the relative advantages of iterative and recursive algorithms for doing
the same task? In this example, the recursive version is certainly shorter because it
does not have to manage a loop computation. Describing the execution of the recursive version makes it sound more complex than the iterative version, but all steps are
carried out automatically. One need not be aware of what is happening internally
except to note that a long series of recursive invocations can use a lot of memory
by storing information relevant to previous invocations on the stack. If too much
memory is consumed, a “stack overflow” can result. Besides using more memory,
recursive algorithms can require many more computations and can run more slowly
than nonrecursive ones (see Exercise 3 in On the Computer at the end of this chapter).
Nonetheless, recursion provides a natural way to think about many problems,
some of which would have very complex nonrecursive solutions. The problem of
computing values for a sequence that has itself been defined recursively is wellsuited to a recursive solution. Many programming languages support recursion.
algorIthm
S(positive integer n)
//function that recursively computes the value S(n)
//for the sequence S of Example 1
if n = 1 then
return 2
else
return 2 * S(n − 1)
end if
end function S