Recursion & BacktrackingEasyO(n) time · O(1) space

Fibonacci

Mahabharata — The Lineage of Kurus — Each Generation Built on the Two Before

प्रत्येक पीढ़ी — दो पूर्व पीढ़ियों का योग। F(n) = F(n-1) + F(n-2) — सृष्टि का सरल नियम॥

*Each generation — sum of the two before. F(n) = F(n-1) + F(n-2) — the simple law of creation.*

The Story

Find the nth Fibonacci number. F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).

For n=8: F(8)=21. Sequence: 0,1,1,2,3,5,8,13,21.

This is the gateway problem to recursion. Three solutions:

**1. Naive Recursion — O(2^n):** ```java int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); } ``` Explosive overlap: fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). fib(3) is computed twice! Tree of calls = 2^n.

**2. Memoization (Top-Down DP) — O(n):** ```java int[] memo = new int[n+1]; Arrays.fill(memo, -1); int fib(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; return memo[n] = fib(n-1) + fib(n-2); } ``` Each subproblem computed exactly once.

**3. Iterative (Bottom-Up DP) — O(n) time, O(1) space:** ```java int fib(int n) { if (n <= 1) return n; int a=0, b=1; for (int i=2; i<=n; i++) { int t=a+b; a=b; b=t; } return b; } ``` No recursion, no extra space. Just two variables rolling forward.

The Kuru dynasty: each king's strength (Fibonacci number) is the sum of the previous two kings' strengths. The naive tree explores every lineage branch redundantly. Memoization prunes this. Iteration avoids the tree entirely.

The Naive Recursive Tree

Recurse: fib(n)=fib(n-1)+fib(n-2). Exponential overlap. O(2^n).

java

public int fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n-1) + fibNaive(n-2);
}

Krishna's Iterative Rolling Wisdom

Two variables a,b track consecutive Fibonacci. Roll forward: t=a+b; a=b; b=t. O(n) time, O(1) space.

java

public int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int t = a + b;
        a = b;
        b = t;
    }
    return b;
}

Step-by-Step Walkthrough

n=0: return 0 ✅
n=1: return 1 ✅
n=2: a=0,b=1,i=2: t=1,a=1,b=1. return 1 ✅

Deep Insight

**Three paradigms of computation:** - **Naive recursion:** Elegant but exponential. Each call spawns two, creating a binary tree of 2^n leaves. - **Memoization:** Add a cache. Each unique subproblem solved once → O(n) calls. Recursive clarity + optimal efficiency. - **Iterative:** Eliminate the call stack entirely. O(1) space. The rolling-two-variables pattern.

**The recursion pattern for all rb-1 to rb-5:** Identify base case(s) and the recursive relationship. Reduce to smaller subproblems.

**Matrix exponentiation (O(log n)):** Advanced approach for huge n using [F(n+1),F(n); F(n),F(n-1)] = [[1,1],[1,0]]^n.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(2^n)	O(n)	Call stack depth n
Optimal	O(n)	O(1)	Iterative two-variable rolling

Pattern Recognition

✅ Fibonacci = simplest recursive recurrence
✅ Naive O(2^n) → memoization O(n) → iterative O(1) space
✅ Base cases: f(0)=0, f(1)=1
✅ Gateway to all DP and recursion problems

**LeetCode Trigger Phrases:**
→ "fibonacci number"
→ nth term of recurrence relation
→ Rolling two-variable DP

Bhagavad Gita 7.10

बीजं मां सर्वभूतानां विद्धि पार्थ सनातनम्।

Know Me to be the eternal seed of all beings, O Partha.

Connection: The Fibonacci sequence grows from two seeds: 0 and 1. Every subsequent number emerges from the two preceding it — an unbroken chain of creation where each generation contains the essence of both parents. Like the eternal seed from which all creation grows, the base cases F(0)=0 and F(1)=1 contain the entire infinite sequence within them. The recursive law F(n) = F(n-1) + F(n-2) is creation's simplest expression.