Course contentsShow
← Java
Lesson 229 of 2,8705. Methods and Function CallsFree lesson

Example: Fibonacci Numbers Using Recursion

Implementing fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) with base cases for 0 and 1.

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):

  1. It needs fibonacci(3) + fibonacci(2)
  2. fibonacci(3) needs fibonacci(2) + fibonacci(1)
  3. fibonacci(2) needs fibonacci(1) + fibonacci(0)
  4. Eventually you hit the base cases (0 and 1), which stop the recursion
  5. 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.