Write a Recursive Function for Fibonacci Number

• Fibonacci sequence – a series where each number equals the sum of the two preceding numbers, starting with zero and one.
• Base cases – fib(0) = 0 and fib(1) = 1 because the recursive case needs two previous values.
• Recursive case – fib(n) = fib(n - 1) + fib(n - 2) makes two recursive calls and sums the results.
• Naive complexity – the call tree branches twice at every level, giving O(2^n) time.
• Memoization fix – caching each result on first computation reduces time to O(n).
• Rolling variables – keeping only the last two values gives O(n) time with O(1) space.

What is the Fibonacci sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two numbers before it. The sequence starts with zero and one, and every number after that follows a simple rule: add the previous two. The first several terms are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

In Java, the definition translates directly into a recursive function with two base cases and one recursive case.

package com.bank.dsa;

public class FibonacciRecursive {

    public static long fib(int n) {
        if (n == 0) return 0;   // base case 1
        if (n == 1) return 1;   // base case 2
        return fib(n - 1) + fib(n - 2);  // recursive case
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.println("fib(" + i + ") = " + fib(i));
        }
    }
}

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

Why is naive recursion slow?

The naive recursive version is beautifully simple but terribly slow. Every call to fib(n) makes two further calls, and each of those makes two more. This creates a binary call tree where the same values are computed again and again. For example, fib(5) calls fib(3) twice and fib(2) three times.

The total number of calls grows exponentially, roughly O(2^n). Computing fib(40) takes over a billion calls. Computing fib(50) would take minutes on a modern machine.

package com.bank.dsa;

public class FibonacciCallCounter {

    private static long callCount = 0;

    public static long fib(int n) {
        callCount++;
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        int n = 30;
        callCount = 0;
        long result = fib(n);
        System.out.println("fib(" + n + ") = " + result);
        System.out.println("Total recursive calls: " + callCount);
    }
}

fib(30) = 832040
Total recursive calls: 2692537

How does memoization fix the problem?

Memoization keeps the natural recursion but adds a cache. Before computing fib(n), we check if the answer is already stored. If it is, we return it immediately. If not, we compute it, store it, and then return it. This ensures each value is computed exactly once.

package com.bank.dsa;

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

public class FibonacciMemoized {

    private static final Map<Integer, Long> memo = new HashMap<>();

    public static long fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (memo.containsKey(n)) return memo.get(n);

        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("fib(50) = " + fib(50));
    }
}

fib(50) = 12586269025

Memoization reduces the time from O(2^n) to O(n) because there are only n distinct subproblems. The space is O(n) for the cache plus O(n) for the recursion stack.

How does the bottom-up iterative approach work?

Instead of starting at n and recursing downward, we start at the base cases and build upward. Since each term depends only on the previous two, we keep just two rolling variables and iterate forward.

package com.bank.dsa;

public class FibonacciBottomUp {

    public static long fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        long prev2 = 0;  // fib(i - 2)
        long prev1 = 1;  // fib(i - 1)

        for (int i = 2; i <= n; i++) {
            long current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
        System.out.println("fib(50) = " + fib(50));
    }
}

fib(10) = 55
fib(50) = 12586269025

This approach runs in O(n) time and O(1) space. There is no recursion stack and no cache. This is the version you should ship in production when only the final value is needed.

How is memoization different from tabulation?

| Aspect | Memoization (top-down) | Tabulation (bottom-up) |
|---|---|---|
| Direction | Starts at n, recurses to base | Starts at base, builds to n |
| Data structure | HashMap or array cache | Array filled in order |
| Stack usage | O(n) recursion stack | No recursion stack |
| Space optimisation | Harder to shrink | Easy to keep only last few values |
| Subproblem coverage | Solves only reachable states | Solves all states up to n |
| Best when | State space is sparse | All states are needed |

package com.bank.dsa;

public class FibonacciTabulation {

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

    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
    }
}

fib(10) = 55

What are the edge cases?

Fibonacci numbers grow exponentially. A long in Java holds values up to about 9.2 times 10 to the 18th power. The 92nd Fibonacci number is 7540113804746346429, which fits in a long, but the 93rd is 12200160415121876738, which overflows silently.

package com.bank.dsa;

import java.math.BigInteger;

public class FibonacciBigInteger {

    public static BigInteger fib(int n) {
        if (n == 0) return BigInteger.ZERO;
        if (n == 1) return BigInteger.ONE;

        BigInteger prev2 = BigInteger.ZERO;
        BigInteger prev1 = BigInteger.ONE;

        for (int i = 2; i <= n; i++) {
            BigInteger current = prev1.add(prev2);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println("fib(93)  = " + fib(93));
        System.out.println("fib(100) = " + fib(100));
    }
}

fib(93)  = 12200160415121876738
fib(100) = 354224848179261915075

Another edge case is negative input. The standard Fibonacci definition does not cover negative numbers. In production code, validate the input and throw an IllegalArgumentException for negative values.

What are common mistakes?

The most common mistake is forgetting both base cases. If you write only if (n == 0) return 0, the function recurses past n == 1 without stopping and causes a StackOverflowError.

// WRONG: missing base case for n == 1
public static long fibWrong(int n) {
    if (n == 0) return 0;
    return fibWrong(n - 1) + fibWrong(n - 2);  // fib(1) calls fib(0) + fib(-1) endlessly
}

// CORRECT: both base cases present
public static long fibCorrect(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibCorrect(n - 1) + fibCorrect(n - 2);
}

Another mistake is using int instead of long. Fibonacci numbers exceed Integer.MAX_VALUE at fib(47), so always use long at minimum.

When should you use each approach?

• Use the naive recursion only to demonstrate understanding of the recurrence in a teaching context.
• Use memoization when the recursion structure is natural and the state space may be sparse.
• Use bottom-up with rolling variables in production when only the final value is needed, as it gives O(1) space.
• Use BigInteger when n can be large enough to overflow a long (n >= 93).

package com.bank.service;

import java.math.BigInteger;

public class LoyaltyBonusCalculator {

    /**
     * Calculates the loyalty bonus for month n at National Bank of India.
     * Month 0 bonus = 0, month 1 bonus = 1 unit, month n = sum of previous two.
     */
    public static BigInteger calculateBonus(int month) {
        if (month < 0) throw new IllegalArgumentException("Month cannot be negative");
        if (month == 0) return BigInteger.ZERO;
        if (month == 1) return BigInteger.ONE;

        BigInteger twoBack = BigInteger.ZERO;
        BigInteger oneBack = BigInteger.ONE;

        for (int i = 2; i <= month; i++) {
            BigInteger current = oneBack.add(twoBack);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }

    public static void main(String[] args) {
        for (int m = 0; m <= 12; m++) {
            System.out.println("Month " + m + " bonus: " + calculateBonus(m) + " units");
        }
    }
}

Month 0 bonus: 0 units
Month 1 bonus: 1 units
Month 2 bonus: 1 units
Month 3 bonus: 2 units
Month 4 bonus: 3 units
Month 5 bonus: 5 units
Month 6 bonus: 8 units
Month 7 bonus: 13 units
Month 8 bonus: 21 units
Month 9 bonus: 34 units
Month 10 bonus: 55 units
Month 11 bonus: 89 units
Month 12 bonus: 144 units

What should a senior engineer know?

A senior engineer should know that the naive recursive Fibonacci is the textbook example of overlapping subproblems. The call tree has O(2^n) nodes but only O(n) distinct subproblems, which is exactly the condition that makes dynamic programming profitable.

The matrix exponentiation method computes fib(n) in O(log n) time by raising the 2x2 Fibonacci matrix to the nth power. This is useful for extremely large n but rarely needed in interviews.

Fibonacci numbers appear in unexpected places: the number of ways to climb stairs with steps of one or two, the number of binary strings without consecutive ones, and the analysis of Euclid's GCD algorithm (worst case inputs are consecutive Fibonacci numbers).

What are common interview follow-up questions?

• How would you compute fib(n) mod M for very large n without overflow?
• Can you compute Fibonacci in O(log n) time using matrix exponentiation?
• How does Fibonacci relate to the climbing stairs problem?
• What is the space complexity of the memoized version versus the rolling version?
• At what value of n does a long overflow for Fibonacci?