RECURSION - Introduction to Java Programming - page 738

20.1 Introduction
Recursion is a technique that leads to elegant solutions to problems that are difficult to
program using simple loops.

Key
Point

Suppose you want to find all the files under a directory that contain a particular word. How do
you solve this problem? There are several ways to do so. An intuitive and effective solution is
to use recursion by searching the files in the subdirectories recursively.
H-trees, depicted in Figure 20.1, are used in a very large-scale integration (VLSI) design as a
clock distribution network for routing timing signals to all parts of a chip with equal propagation
delays. How do you write a program to display H-trees? A good approach is to use recursion.

search word problem

H-tree problem

(a) (b) (c) (d)

F IGURE 20.1

An H-tree can be displayed using recursion.

To use recursion is to program using recursive methods —that is, to use methods that
invoke themselves. Recursion is a useful programming technique. In some cases, it enables
you to develop a natural, straightforward, simple solution to an otherwise difficult problem.
This chapter introduces the concepts and techniques of recursive programming and illustrates
with examples of how to “think recursively.”

recursive method

20.2 Case Study: Computing Factorials
A recursive method is one that invokes itself.

Key
Point

Many mathematical functions are defined using recursion. Let's begin with a simple example.
The factorial of a number n can be recursively defined as follows:

0! = 1;
n! = n × (n - 1)!; n > 0

How do you find n! for a given n ? To find 1! is easy, because you know that 0! is 1 , and 1!
is 1 × 0! . Assuming that you know (n - 1)! , you can obtain n! immediately by using n ×
(n - 1)! . Thus, the problem of computing n! is reduced to computing (n - 1)! . When
computing (n - 1)! , you can apply the same idea recursively until n is reduced to 0 .
Let factorial(n) be the method for computing n! . If you call the method with n = 0 ,
it immediately returns the result. The method knows how to solve the simplest case, which is
referred to as the base case or the stopping condition . If you call the method with n > 0 , it
reduces the problem into a subproblem for computing the factorial of n - 1 . The subproblem
is essentially the same as the original problem, but it is simpler or smaller. Because the sub-
problem has the same property as the original problem, you can call the method with a differ-
ent argument, which is referred to as a recursive call .
The recursive algorithm for computing factorial(n) can be simply described as follows:

base case or stopping
condition

recursive call

if (n == 0 )
return 1 ;