Example: Fibonacci Numbers Using Recursion
You'll learn how to implement the classic Fibonacci sequence using a recursive method with multiple base cases.
What is the Fibonacci Sequence?
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21...
Mathematically:
- fibonacci(0) = 0
- fibonacci(1) = 1
- fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) for n > 1
This is a perfect problem for recursion because each Fibonacci number is naturally defined in terms of smaller Fibonacci numbers.
Implementing Fibonacci Recursively
Here's the recursive implementation:
public static int fibonacci(int n) {
// Base case 1: fibonacci(0) is 0
if (n == 0) {
return 0;
}
// Base case 2: fibonacci(1) is 1
if (n == 1) {
return 1;
}
// Recursive case: sum of the two previous numbers
return fibonacci(n - 1) + fibonacci(n - 2);
}
How It Works
When you call fibonacci(4):
- It needs
fibonacci(3) + fibonacci(2) fibonacci(3)needsfibonacci(2) + fibonacci(1)fibonacci(2)needsfibonacci(1) + fibonacci(0)- Eventually you hit the base cases (0 and 1), which stop the recursion
- The results bubble back up, adding together
Notice we have two base cases here—both 0 and 1 must return directly to anchor the recursion. Without both, the method would eventually try to compute fibonacci(-1) and continue infinitely downward.
Key Takeaway: The Fibonacci method demonstrates recursion with two base cases (n=0 and n=1) and a recursive case that makes two recursive calls, naturally mirroring the mathematical definition of the sequence.