Java Program for Fibonacci Using Recursion

You can write a Java program to find Fibonacci numbers using recursion by defining a method like int fibonacci(int n) { if (n <= 1) return n; else return fibonacci(n-1) + fibonacci(n-2); } which calls itself to calculate the sequence.

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the Fibonacci number at position n, think of the sequence as starting with 0 and 1. Each next number is the sum of the two before it. Using recursion means the function calls itself with smaller numbers until it reaches the base cases where n is 0 or 1, which are known values.

Algorithm

1

Get the input number n.

2

If n is 0 or 1, return n as the Fibonacci number.

3

Otherwise, call the function recursively for (n-1) and (n-2).

4

Add the results of these two calls.

5

Return the sum as the Fibonacci number for n.

Code

java

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci number at position " + n + " is " + fibonacci(n));
    }
}

Output

Fibonacci number at position 10 is 55

Dry Run

Let's trace fibonacci(4) through the code

1

Call fibonacci(4)

Since 4 > 1, call fibonacci(3) + fibonacci(2)

2

Call fibonacci(3)

Since 3 > 1, call fibonacci(2) + fibonacci(1)

3

Call fibonacci(2)

Since 2 > 1, call fibonacci(1) + fibonacci(0)

4

Call fibonacci(1)

Return 1 (base case)

5

Call fibonacci(0)

Return 0 (base case)

6

Calculate fibonacci(2)

1 + 0 = 1

7

Call fibonacci(1)

Return 1 (base case)

8

Calculate fibonacci(3)

1 + 1 = 2

9

Call fibonacci(2)

From previous calculation, fibonacci(2) = 1

10

Calculate fibonacci(4)

2 + 1 = 3

Call	Returned Value
fibonacci(1)	1
fibonacci(0)	0
fibonacci(2)	1
fibonacci(1)	1
fibonacci(3)	2
fibonacci(2)	1
fibonacci(4)	3

Why This Works

Step 1: Base Case

The function returns n directly when n is 0 or 1, stopping the recursion.

Step 2: Recursive Calls

For other values, the function calls itself twice with n-1 and n-2 to build the Fibonacci sequence.

Step 3: Combining Results

The results of the two recursive calls are added to get the Fibonacci number at position n.

Alternative Approaches

Iterative approach

java

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci number at position " + n + " is " + fibonacci(n));
    }
}

This method uses a loop and is faster and uses less memory than recursion.

Memoization (top-down dynamic programming)

java

import java.util.HashMap;
public class Fibonacci {
    private static HashMap<Integer, Integer> memo = new HashMap<>();
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci number at position " + n + " is " + fibonacci(n));
    }
}

This method caches results to avoid repeated calculations, improving performance over simple recursion.

Complexity: O(2^n) time, O(n) space

Time Complexity

The simple recursive method calls itself twice for each non-base case, leading to exponential time as calls grow rapidly.

Space Complexity

The recursion stack can go as deep as n, so space complexity is O(n).

Which Approach is Fastest?

Iterative and memoized methods run in O(n) time and are much faster than simple recursion.

Approach	Time	Space	Best For
Simple Recursion	O(2^n)	O(n)	Learning recursion basics
Iterative	O(n)	O(1)	Efficient calculation with low memory
Memoization	O(n)	O(n)	Fast recursion with caching