Recursive Calls

A method normally executes statements that may include calls to other methods. However, it is occasionally convenient to have a method call itself. This scenario is known as recursion.

For example, suppose you need to write a method that returns a factorial (the product of all the positive integers up to and including a specific integer). For example, 3! (the ! is the mathematical symbol for factorial) equals 3x2x1 or 6.

Your first approach to writing this method might consist of the code presented in Listing 2-43.

Listing 2-43. A nonrecursive approach to obtaining a factorial int factorial(int n) {

product *= i; return product;

Although this code accomplishes its task, factorial() could also be written in Listing 2-44's recursive style.

Listing 2-44. A recursive approach to obtaining a factorial int factorial(int n) {

return 1; // base problem else return n*factorial(n-1);

The recursive approach takes advantage of being able to express a problem in simpler terms of itself. According to Listing 2-44, the simplest problem, which is also known as the base problem, is 1! (1).

When an argument greater than 1 is passed to factorial(), this method breaks the problem into a simpler problem by calling itself with the next smaller argument value. Eventually, the base problem will be reached.

For example, calling factorial(4) results in the following stack of expressions:

4*factorial(3) 3*factorial(2) 2*factorial(l)

This last expression is at the top of the stack. When factorial(l) returns 1, these expressions are evaluated as the stack begins to unwind:

2*factorial(l) now becomes 2*1 (2)

3*factorial(2) now becomes 3*2 (6)

4*factorial(3) now becomes 4*6 (24)

Recursion provides an elegant way to express many problems. Additional examples include searching tree-based data structures for specific values and, in a hierarchical file system, outputting the names of all files that contain specific text.

CAUTION: Recursion consumes stack space, so make sure that your recursion eventually ends in a base problem; otherwise, you will run out of stack space and your application will terminate.

Was this article helpful?

0 0

Post a comment