Skip to content

Fibonacci Number

LeetCode

01 · Question

For a nonnegative integer n, return F(n), where F(0)=0, F(1)=1, and F(n)=F(n−1)+F(n−2) for n>1.

Examples: n=0 → 0; n=1 → 1; n=4 → 3; n=10 → 55. Go results must fit int.

02 · Analysis

Naive recursion: the same states are recomputed many times. O(2^n) time is a valid upper bound (the tighter growth is Θ(φ^n)); the active stack is only O(n). Use it to understand the recurrence, not for large inputs.

Memoization: each state from 0 to n is computed once, giving O(n) time and O(n) cache plus stack space. The cache belongs to this invocation. A zero result must still count as a cache hit; test key presence, not truthiness.

Iteration: evaluate states in increasing order while retaining only the preceding two. O(n) time and O(1) auxiliary space. These complexities count arithmetic operations on fixed-width values. Memoization still has linear depth and does not remove recursion-limit concerns.

03 · Solution

Reference solution

1. Naive recursion: repeated work

1def fib(n: int) -> int:
2    if n <= 1:
3        return n
4    return fib(n - 1) + fib(n - 2)

2. Memoization: compute each state once

1def fib(n: int) -> int:
2    memo = {0: 0, 1: 1}
3    def visit(i):
4        if i not in memo:
5            memo[i] = visit(i - 1) + visit(i - 2)
6        return memo[i]
7    return visit(n)

3. Iteration: keep only two values

1def fib(n: int) -> int:
2    if n <= 1:
3        return n
4    previous, current = 0, 1
5    for _ in range(2, n + 1):
6        previous, current = current, previous + current
7    return current
Previous
Laminal Arrays
Next
Pow(x, n)