(^638) | Recursion
Call 2:xis equal to 2 and nis equal to 2. Because nis not equal to 1, the method poweris
called again, this time with xand n 1 as arguments. Execution of Call 2 pauses until an an-
swer is sent back from this recursive call.
Call 3:xis equal to 2 and nis equal to 1. Because nequals 1, the value of xis returned. This
call to the method has finished executing, and the method return value (which is 2) is passed
back to the place in the statement from which the call was made in Call 2.
Call 2:This call to the method can now complete the statement that contained the recursive
call because the recursive call has returned. Call 3’s return value (which is 2) is multiplied by
x. This call to the method has finished executing, and the method return value (which is 4) is
passed back to the place in the statement from which the call was made in Call 1.
Call 1:This call to the method can now complete the statement that contained the recur-
sive call because the recursive call has returned. Call 2’s return value (which is 4) is multiplied
by x. This call to the method has finished executing, and the method return value (which is 8)
is passed back to the place in the statement from which the call was made. Because the first
call (the nonrecursive call) has now completed, 8 is the final value of the method power.
What happens if no base case exists? We have infinite recursion, the recursive
equivalent of an infinite loop. For example, if the condition
if (n == 1)
were omitted,powerwould be called over and over again forever. Infinite recursion
also occurs if we call powerwith nless than or equal to 0.
In actuality, recursive calls can’t go on forever. Here’s why. When we call a method, ei-
ther recursively or nonrecursively, the computer system creates temporary storage for the
parameters and the method’s (automatic) local variables. This temporary storage is a region
of memory called the run-time stack. When the method returns, its parameters and local
variables are released from the run-time stack. With infinite recursion, the recursive method
calls never return. Each time the method calls itself, a little more of the run-time stack is used
to store the new copies of the variables. Eventually, the memory space on the stack runs
out. At that point, the program crashes with an error message such as “RUN-TIME STACK
OVERFLOW” (or the application may simply freeze).
13.2 More Examples with Simple Variables
For some people, thinking recursively is intuitive; for others, it is a mysterious process verg-
ing on the supernatural. The objective of the rest of this chapter is to demystify the recur-
sive process by working through a collection of examples.Calculating the Factorial Function
Let’s look at another example: calculating a factorial. The factorial of a number n(written n!)
is nmultiplied by n1,n2,n3, and so on. Another way of expressing a factorial is
n! = n* (n 1)!
This expression looks like a recursive definition. The term (n1)! is a smaller instance
of n!—that is, it takes one less multiplication to calculate (n1)! than it does to calculate n!Infinite recursion The situa-
tion in which a method calls it-
self over and over endlessly