Java Language Tutorial => The basic idea of recursion

Example

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:

There must be a base condition for the problem, which will be the endpoint for the recursion. When a recursive function reaches the base condition, it makes no further (deeper) recursive calls.
Each level of recursion should be attempting a smaller problem. The recursive function thus divides the problem into smaller and smaller parts. Assuming that the problem is finite, this will ensure that the recursion terminates.

In Java there is a third precondition: it should not be necessary to recurse too deeply to solve the problem; see 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.}

PDF - Download Java Language for free

Previous Next

Java Language

Fastest Entity Framework Extensions

Example

Got any Java Language Question?

Java Language

Java Language Recursion The basic idea of recursion

Fastest Entity Framework Extensions

Example

Got any Java Language Question?