How does recursion work in Java, and what are the two conditions every recursive method needs?
Recursion is when a method calls itself. Each call works on a smaller piece of the problem, and the calls keep going until the smallest piece is reached, which is the case that the method handles without calling itself again.
Every recursive method needs two things, and without either of them the method never stops.
The first one is the base case. This is the case where the method returns an answer without calling itself again. It is the bottom of the recursion.
The second one is the recursive case. This is where the method calls itself with a smaller or simpler input, so that each call moves towards the base case.
public class Main {
public static void main(String[] args) {
for (int number = 0; number <= 5; number++) {
System.out.println(number + "! = " + factorial(number));
}
}
// The base case is number == 0.
// The recursive case is number * factorial(number - 1).
static int factorial(int number) {
if (number == 0) {
return 1;
}
return number * factorial(number - 1);
}
}
When you read that method, follow it like this. The call factorial(5) is not 5 times factorial(4) yet, because Java has to work out factorial(4) first. That call needs factorial(3), and that one needs factorial(2), and so on, until factorial(0) reaches the base case and gives back 1. Then the answers come back up the stack, and each one multiplies its own number into the answer it was given.
Recursion is worth using when the problem is naturally split into smaller versions of itself, such as walking a tree structure or working through a list. It is worth avoiding when a simple loop would do, because every call costs a stack frame.
The last question in this topic looks at what to do when the data is too deep for the stack.