Recursion - Absolute Java - page 667

11.3 Thinking Recursively

There are two kinds of people in the world, those who divide the world into
two kinds of people and those who do not.

ANONYMOUS

Recursive Design Techniques
When defining and using recursive methods, you do not want to be continually aware
of the stack and the suspended computations. The power of recursion comes from the
fact that you can ignore that detail and let the computer do the bookkeeping for you.
Consider the example of the method power in Display 11.3. The way to think of the
definition of power is as follows:

power(x, n) returns power(x, n - 1)*x

Because x n is equal to x n - 1 *x , this is the correct value to return, provided that the
computation will always reach a stopping case and will correctly compute the stopping
case. So, after checking that the recursive part of the definition is correct, all you need
to check is that the chain of recursive calls will always reach a stopping case and that the
stopping case will always return the correct value. In other words, all that you need to
do is check that the following three properties are satisfied:
1. There is no infi nite recursion. (A recursive call may lead to another recursive
call, which may lead to another, and so forth, but every such chain of recursive
calls eventually reaches a stopping case.)
2. Each stopping case returns the correct value for that case.
3. For the cases that involve recursion: if all recursive calls return the correct value,
then the fi nal value returned by the method is the correct value.
For example, consider the method power in Display 11.3 :
1 . There is no infinite recursion : The second argument to power(x, n) is
d ecreased by one in each recursive call, so any chain of recursive calls must eventually
reach the case power(x, 0) , which is the stopping case. Thus, there is no infi nite
recursion.
2 . Each stopping case returns the correct value for that case : The only stopping
case is power(x, 0) . A call of the form power(x, 0) always returns 1 , and the
correct value for x 0 is 1 . So, the stopping case returns the correct value.
3 . For the cases that involve recursion, if all recursive calls return the correct
value, then the final value returned by the method is the correct value : The only
case that involves recursion is when n > 1 . When n > 1 , power(x, n) returns
power(x, n - 1)*x .

criteria for
methods that
return a value