What is Recursion?
Recursion is a programming technique where a function calls itself. It allows problems to be broken down into smaller subproblems. Each subproblem can either be broken down further or solved directly.
(Image from theburningmonk.com)
Example: Factorial
Definition
In math, the factorial of a whole number N
is defined as the product of all integers from 1
to N
. The factorial of N
is written as N!
. For example,
1! = 1
2! = 2x1 = 2
3! = 3x2x1 = 6
4! = 4x3x2x1 = 24
Additionally, by definition, 0!
(a special case) is equal to 1
.
Recursive definition
Factorial can also be defined recursively:
0! = 1
N! = N * (N-1)!
Stepping through the recursive definition
Using the recursive definition, let’s see what happens when we try to calculate 4!
:
4! = 4 * (4-1)! = 4 * 3!
- We need the value of
3!
:3! = 3 * 2!
- We need the value of
2!
:2! = 2 * 1!
- We need the value of
1!
:1! = 1 * 0!
- We need the value of
0!
:0! = 1
(by definition) - Backtrack to step 4:
1! = 1 * 1 = 1
- Backtrack to step 3:
2! = 2 * 1 = 2
- Backtrack to step 2:
3! = 3 * 2 = 6
- Backtrack to step 1:
4! = 4 * 6 = 24
In this example, 0!
is known as the base case. The base case is a problem which can be solved without making any recursive calls. All recursive functions require a base case in order to terminate; without a base case, the recursion would be infinite.
Once the base case has been reached, the program backtracks through all the recursive calls, solving each intermediate problem (1!
, 2!
, 3!
), and eventually returning to solve the original problem (4!
).
The code
Now it’s time to code a recursive factorial()
function in Java. The Java code looks very similar to the mathematical definition: (download a full working example)
public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
Conclusion
In conclusion, recursion allows us to split a problem into multiple smaller problems, whose solutions can be combined to give us the solution to the original problem. This strategy can help us avoid being overwhelmed by a complex problem, and lets us to write an elegant solution that solve the problem in small steps.