Generate Fibonacci Series up to N Terms - Java

Category: Easy | Concepts used: Iteration window sliding, recursive stack processing, memoization lookup

---

Problem Statement

Generate the first N terms of the Fibonacci series, where each number is the sum of the two preceding it, starting with seed values 0, 1.

Input : N = 5      Output: 0 1 1 2 3
Input : N = 1        Output: 0

Examples (with edge scenarios)

#	N	Output	Why
1	5	0 1 1 2 3	Standard sequence
2	1	0	First term only
3	0	(nothing)	Empty count requested
4	2	0 1	Seed values only
5	10	0 1 1 2 3 5 8 13 21 34	Large sequence

⚠️ Common Beginner Mistake

Mistake	Impact	Fix
Not verifying boundaries for N <= 0	Array index or stack overflows	Add an early return guard check for non-positive inputs
Implementing naive recursion for large N values	Severe CPU throttling due to redundant calculations, causing stack exhaustion	Use loops or recursive caching (memoization)

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether zero and negative values are allowed, how large the input can be, and what should happen when an arithmetic result exceeds the chosen Java type. The examples use the contract stated in this article, but an interview answer should say these assumptions aloud.

Analogy: The Rabbit Population Growth

Fibonacci numbers were originally formulated in 1202 to model the growth of a rabbit population:

• Start with a single newborn pair of rabbits in a field (0 pairs).
• After one month, they grow and mature into a mating pair (1 pair).
• After the second month, they reproduce and give birth to a new pair, resulting in 2 pairs total.
• Every month, each mature pair gives birth to a new pair, while the newborns mature.
• The number of pairs in any month is the sum of the mature pairs (who were alive two months ago) and all pairs from last month!

---

Solution 1 — Iterative (Loop-based, Recommended)

This is the standard, most memory-efficient approach.

Intuition

To find the next term, we only need to track the last two numbers (first and second). By maintaining a sliding window, we calculate the next term, slide the references forward, and repeat in (O(N)) time and (O(1)) auxiliary memory.

public class FibonacciIterative {
    public static void printFibonacci(int n) {
        if (n <= 0) {
            return; // Guard check
        }

int first = 0, second = 1;

for (int i = 0; i < n; i++) {
            System.out.print(first + " ");
            int next = first + second; // Calculate next term
            first = second;            // Slide window forward
            second = next;
        }
    }

public static void main(String[] args) {
        printFibonacci(5); // 0 1 1 2 3
        System.out.println();
        printFibonacci(1);  // 0
        System.out.println();
        printFibonacci(0);   // (nothing)
    }
}

Output:

0 1 1 2 3
0

---

Solution 2 — Recursive (Naive, Inefficient)

This approach translates the mathematical recurrence relation directly into code.

Intuition

The series is defined as: $\text{Fib}(n) = \text{Fib}(n-1) + \text{Fib}(n-2) \quad \text{where} \quad \text{Fib}(0)=0, \text{Fib}(1)=1$

While code-wise elegant, this results in an exponential recursive call tree with massive redundancy.

public class FibonacciRecursive {
    public static int 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); // Recurrence branch
    }

public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            System.out.print(fib(i) + " "); // 0 1 1 2 3
        }
    }
}

---

Solution 3 — Recursive with Memoization (Optimal Recursion)

This optimization caches subproblem results.

Intuition

By storing the result of fib(k) in a map after the first calculation, any future call for k becomes a constant-time (O(1)) lookup. This collapses the exponential call tree into a linear chain.

import java.util.HashMap;

public class FibonacciMemoized {
    private static HashMap<Integer, Integer> memo = new HashMap<>();

public static int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (memo.containsKey(n)) {
            return memo.get(n); // Return cached result
        }

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

public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.print(fib(i) + " "); // 0 1 1 2 3 5 8 13 21 34
        }
    }
}

---

📊 Visual Recursive Call Tree (Redundancy Chart)

This tree shows why Solution 2 is so slow: fib(2) and fib(1) are re-evaluated multiple times independently.

graph TD
    F4["fib(4)"] --> F3["fib(3)"]
    F4 --> F2_1["fib(2)"]
    F3 --> F2_2["fib(2)"]
    F3 --> F1_1["fib(1)"]
    F2_1 --> F1_2["fib(1)"]
    F2_1 --> F0_1["fib(0)"]
    F2_2 --> F1_3["fib(1)"]
    F2_2 --> F0_2["fib(0)"]
    style F2_1 fill:#ffcccb,stroke:#333
    style F2_2 fill:#ffcccb,stroke:#333

---

Interviewer Insights

This is a classic question evaluating algorithmic execution footprints and recursive stack cost.

Follow-up questions you might get:

• “What is the time complexity of the naive recursive solution?” → It is (O(2^N)). The number of operations doubles with each increase in (N), which becomes unusable for (N > 40). Memoization reduces this to (O(N)).
• “Which solution is best for space efficiency?” → Solution 1 (Iterative). It runs in (O(1)) space. Even memoized recursion takes (O(N)) space for the cache map and stack frame allocation.

---

Quick Recap

Approach	Time Complexity	Space Complexity	Stack Frame Overhead?	Interview Signal
Iterative	(O(N))	(O(1))	No	Highly optimal, production standard
Naive Recursion	(O(2^N))	(O(N)) (call stack)	Yes	Elegant math expression, but poor performance
Memoization	(O(N))	(O(N)) (cache + stack)	Yes	Demonstrates dynamic programming fundamentals