Algorithms Functions Recursion

The idea of calling one function from another immediately suggests the possibility of a function calling itself. The function-call mechanism in Java supports this possibility, which is known as recursion. Recursion is a powerful general-purpose programming technique, and is the key to numerous critically important computational applications, ranging from combinatorial search and sorting methods methods that provide basic support for information processing (Chapter 4) to the Fast Fourier Transform for signal processing (Chapter 9).

Your first recursive program.

The HelloWorld for recursion is to implement the factorial function, which is defined for positive integers N by the equation

N! = N × (N-1) × (N-2) × ... × 2 × 1

N! is easy to compute with a for loop, but an even easier method in Factorial.java is to use the following recursive function:

public static int factorial(int N) { if (N == 1) return 1; return N * factorial(N-1); }

You can persuade yourself that it produces the desired result by noting that factorial() returns 1 = 1! when N is 1 and that if it properly computes the value

(N-1)! = (N-1) × (N-2) × ... × 2 × 1

then it properly computes the value

N! = N × (N-1)! = N × (N-1) × (N-2) × ... × 2 × 1

We can trace this computation in the same way that we trace any sequence of function calls.

factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 120

Our factorial() implementation exhibits the two main components that are required for every recursive function.

• The base case returns a value without making any subsequent recursive calls. It does this for one or more special input values for which the function can be evaluated without recursion. For factorial(), the base case is N = 1.
• The reduction step is the central part of a recursive function. It relates the function at one (or more) inputs to the function evaluated at one (or more) other inputs. Furthermore, the sequence of parameter values must converge to the base case. For factorial(), the reduction step is N * factorial(N-1) and N decreases by one for each call, so the sequence of parameter values converges to the base case of N = 1.

Mathematical induction.

Recursive programming is directly related to mathematical induction, a technique for proving facts about discrete functions. Proving that a statement involving an integer N is true for infinitely many values of N by mathematical induction involves two steps.

• The base case is to prove the statement true for some specific value or values of N (usually 0 or 1).
• The induction step is the central part of the proof. For example, we typically assume that a statement is true for all positive integers less than N, then use that fact to prove it true for N.

Such a proof suffices to show that the statement is true for all N: we can start at the base case, and use our proof to establish that the statement is true for each larger value of N, one by one.