What is recursion:
In general, recursion is when a function invokes itself, either directly or indirectly. For example:
// This method calls itself "infinitely"
public void useless() {
useless(); // method calls itself (directly)
}
Conditions for applying recursion to a problem:
There are two preconditions for using recursive functions to solving a specific problem:
In Java there is a third precondition: it should not be necessary to recurse too deeply to solve the problem; see http://stackoverflow.com/documentation/java/914/recursion/15048/deep-recursion-is-problematic-in-java
Example
The following function calculates factorials using recursion. Notice how the method factorial
calls itself within the function. Each time it calls itself, it reduces the parameter n
by 1. When n
reaches 1 (the base condition) the function will recurse no deeper.
public int factorial(int n) {
if (n <= 1) { // the base condition
return 1;
} else {
return n * factorial(n - 1);
}
}
This is not a practical way of computing factorials in Java, since it does not take account of integer overflow, or call stack overflow (i.e. StackOverflowError
exceptions) for large values of n
.