Fibonacci using recursion in Java

Fibonacci using recursion in Java

What is Fibonacci?

The Fibonacci sequence is defined as: F(0)=0,F(1)=1F(0) = 0, \quad F(1) = 1 F(n)=F(n−1)+F(n−2)for n≥2F(n) = F(n-1) + F(n-2) \quad \text{for } n \geq 2

So, the sequence looks like:
0, 1, 1, 2, 3, 5, 8, 13, 21 …

Recursive Idea

  1. Base cases:
    • If n == 0, return 0.
    • If n == 1, return 1.
  2. Recursive case:
    • fib(n) = fib(n-1) + fib(n-2)

Java Code

public class FibonacciRecursion {
    // Recursive method for nth Fibonacci number
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0; // Base case
        } else if (n == 1) {
            return 1; // Base case
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
        }
    }

    public static void main(String[] args) {
        int terms = 10; // print first 10 Fibonacci numbers
        System.out.print("Fibonacci series up to " + terms + " terms: ");
        for (int i = 0; i < terms; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

Output

Fibonacci series up to 10 terms: 0 1 1 2 3 5 8 13 21 34

⚠️ Note: Recursive Fibonacci is simple but inefficient for large n because it recalculates the same values many times. For efficiency, we often use Dynamic Programming (DP) or iteration.

Leave a Reply