Example: Computing Factorial Recursively
You'll learn how to implement a real recursive method that calculates factorials, combining the base case and recursive case patterns.
Now that you understand recursion's structure, let's see it in action with a classic example: computing factorial. Remember, factorial of a number n (written as n!) means multiplying all positive integers from 1 to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.
The Recursive Definition
Mathematically, factorial has a natural recursive definition:
- Base case:
0! = 1(by definition) - Recursive case:
n! = n × (n-1)!
This translates beautifully into Java:
public static int factorial(int n) {
if (n == 0) {
return 1; // Base case: stop the recursion
}
return n * factorial(n - 1); // Recursive case: call ourselves
}
How It Works
When you call factorial(4), here's what happens:
factorial(4)→ 4 is not 0, so return4 * factorial(3)factorial(3)→ return3 * factorial(2)factorial(2)→ return2 * factorial(1)factorial(1)→ return1 * factorial(0)factorial(0)→ base case! return1
Now the returns unwind: 1 * 1 = 1, then 2 * 1 = 2, then 3 * 2 = 6, finally 4 * 6 = 24.
The base case (n == 0) is crucial—without it, the method would call itself forever. Each recursive call works on a smaller problem (n - 1), gradually moving toward the base case.
Key Takeaway: Factorial demonstrates recursion's power: define the simplest case (0! = 1), then express each problem in terms of a simpler version (n! = n × (n-1)!), and Java handles the rest through the call stack.