Java For Dummies Quick Reference

Recursion

Recursion is a basic programming technique in which a method calls itself to solve some problem. A method that uses this technique is recursive. Many programming problems can be solved only by recursion, and some problems that can be solved by other techniques are better solved by recursion.

One of the classic problems for introducing recursion is calculating the factorial of an integer. The factorial of any given integer — I’ll call it n so that I sound mathematical — is the product of all the integers from 1 to n. Thus, the factorial of 5 is 120: 5 × 4 × 3 × 2 × 1.

The recursive way to look at the factorial problem is to realize that the factorial for any given number n is equal to n times the factorial of n–1, provided that n is greater than 1. If n is 1, the factorial of n is 1.

This definition of factorial is recursive because the definition includes the factorial method itself. It also includes the most important part of any recursive method: an end condition. The end condition indicates when the recursive method should stop calling itself. In this case, when n is 1, it just returns 1. Without an end condition, the recursive method keeps calling itself forever.

Here’s the recursive version of the factorial method:

private static long factorial(int n)

{

if (n == 1)

return 1;

else

return n * factorial(n-1);

}