AP Computer Science :: Lessons :: Recursion
Chapter 7:
Pages 338 - 348
Fundamentals of Java
Chapter 12
Pages 455 - 467
Recursive Methods
A method is said to be recursive if it calls itself. This may sound weird, but we have actually used it before in the Fraction project with the gcf method. Most recursive methods can be written without recursion, but they are generally longer and more complex without it. Below is an example of a recursive method for determining factorials:
int factorial(int n) {
if (n == 1)
return 1;
else
return n * factorial(n - 1);
}
The factorial method calculates the product of all positive integers less than or equal to n, which it does by calling the factorial method over and over again. Here is how the same method could be written iteratively, or without recursion:
int factorial(int n) {
int product = 1;
for (int i = 2; i <= n; i++)
product = product * i;
return product;
}
The iterative method is a little longer, and actually seems a little more difficult to understand if we try walking through the recursive method. Let's try walking through our recursive method to see how it works.
Tracing Recursion
Let's follow each step of our recursive factorial method by finding 5!.
factorial(5) calls factorial(4) calls factorial(3) calls factorial(2) calls factorial(1) which returns 1 which returns 2 * 1 = 2 which returns 3 * 2 = 6 which returns 4 * 6 = 24 which returns 5 * 24 = 120
The result of a recursive call isn't known until the final call returns a value. It then progresses back through the previous calls until the first call can return a value. It is very easy to create an infinite loop using recursion so it is important to make sure your calls will always return a value.
Fibonacci
The Fibonacci sequence is a famous sequence of numbers that looks like the following:
0, 1, 1, 2, 3, 5, 8, 13, 21,...
The sequence starts with 0 for number 0 and 1 for number 1, and each of the following numbers is the sum of the previous two. This is fairly easy to calculate using recursion:
int fibonacci(int n) {
if (n == 0 || n == 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Try tracing out this method on paper. It will be a little different than with the factorial method since there are two recursive calls each time the method runs. Your trace should look more like a tree than the previous trace.
