Fibonacci Number

Problem Link

Fibonacci Number – LeetCode

Problem: Fibonacci Number

Problem Statement

The Fibonacci numbers, commonly denoted F(n), form a sequence such that:

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) for n > 1

Given n, return the value of F(n).

Examples

Example 1
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1

Example 2
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2

Example 3
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3

Constraints

0 <= n <= 30

Intuition

The Fibonacci sequence is naturally recursive:
To compute F(n), we need the values of F(n - 1) and F(n - 2).

We can apply recursion directly and explain the flow using the Induction – Base Case – Hypothesis structure.

Induction – Base Case – Hypothesis Method

Function Signature

int fib(int n)

Base Case

If n == 0, return 0
If n == 1, return 1

These are the starting values of the Fibonacci sequence.

Hypothesis

Assume that the recursive calls fib(n - 1) and fib(n - 2) correctly return the (n - 1)th and (n - 2)th Fibonacci numbers.

Induction

Then, by the definition of the Fibonacci sequence, we can return:

fib(n) = fib(n - 1) + fib(n - 2)

Code (Java)

class Solution {
    public int fib(int n) {
        // Base Case
        if (n == 0) return 0;
        if (n == 1) return 1;

        // Hypothesis and Induction
        int first = fib(n - 1);
        int second = fib(n - 2);
        return first + second;
    }
}

Time and Space Complexity

Time Complexity: O(2^n)
- Because each call makes two recursive calls, leading to an exponential number of total calls.
Space Complexity: O(n)
- Due to recursive call stack up to depth n.

Note: For large n, this recursive approach is inefficient. Use memoization or iterative DP for optimization.

Dry Run

Input: `n = 4`

Call stack:

fib(4)
→ fib(3) + fib(2)
→ fib(2) + fib(1) + fib(1) + fib(0)
→ fib(2) = 1, fib(3) = 2
→ fib(4) = 3

Conclusion

The Fibonacci problem is one of the most fundamental recursion exercises. It clearly demonstrates the Induction – Base – Hypothesis reasoning in recursive function design. While the naive solution has exponential time, it lays the groundwork for optimized techniques like memoization and DP.