Fibonacci Series Using Recursive function

Fibonacci series implementation in java is frequently asked question in interview at fresher level. Moreover, it is a very famous example to show how to use recursive function in java.

Recursive Approach

public class Fibonacci {

	public static void main(String[] args) {
		fibonacci(10);
	}

	/**
	 * print fibonacci series from 0 to n
	 * @param n
	 */
	private static void fibonacci(int n) {
		for (int i = 0; i <= n; i++) {
			System.out.print(fib(i) + ", ");
		}
	}

	/**
	 * Recursive approach f(n) = f(n-1) + f(n-2)
	 * @param n
	 * @return
	 */
	public static int fib(int n) {
		if (n <= 1) {
			return n;
		}
		return fib(n - 1) + fib(n - 2);
	}
}

Output
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 

fib(n) recomputes the same values over and over — fib(5) calls fib(3) twice, fib(2) three times, and so on, because neither call knows the other already did (or will do) the same work. The call tree branches twice per level, so recursive approach time complexity is approx 𝘖(2ⁿ). Space complexity is only 𝘖(n) though, since the call stack only ever holds the current chain of pending calls (one path from root to leaf), not the whole tree at once.

Memoized (Top-Down) Approach

We can keep the exact same recursive shape and still eliminate the repeated work, by caching each result the first time it’s computed:

import java.util.HashMap;
import java.util.Map;

public static int fibMemo(int n, Map<Integer, Integer> memo) {
    if (n <= 1) {
        return n;
    }
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    int result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, result);
    return result;
}

Output
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 

Because every value from 0 to n is now computed exactly once and reused on every later call, this brings the time complexity down to 𝘖(n) — at the cost of 𝘖(n) extra space for the memo map, in addition to the 𝘖(n) call stack.

Dynamic Approach

We can use dynamic approach for linear time complexity i.e. 𝘖(n)

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int[] fib = new int[n + 1];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

Output
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 

This iterative version keeps the memoized version’s 𝘖(n) time, but needs no map and no call stack — it only ever looks at the previous two entries, so if you don’t need the whole history you can drop the array and keep just two rolling variables for 𝘖(1) extra space.

Edge Cases

Negative input isn’t rejected. All three versions share the same base case, n <= 1, which also matches negative numbers — fib(-5) simply returns -5 instead of throwing or signaling an error. If n can come from user input, validate it’s non-negative before calling any of these; otherwise the caller just gets a nonsense answer instead of a clear failure.

int overflows silently. fib(46) is 1836311903, which still fits in a 32-bit int. But fib(47) is 2971215073 — that overflows int and wraps around to -1323752223, with no exception at all. Verified directly: calling fibonacci(47) above returns -1323752223, while computing the same sequence with long accumulators gives the true value, 2971215073. Past fib(46), switch int to long (safe up to fib(92)) or to BigInteger if you need terms beyond that.