Problem 12.1 · RecursionEasy

Fibonacci Number

What it teaches: The same problem in three costs: exponential recursion, memoised recursion, and an O(1)-space loop.

Practise it on judges as “Fibonacci Number”.

The problem

F(0) = 0, F(1) = 1, and F(n) = F(n − 1) + F(n − 2). Given n, return F(n).

Example 1

Input: n = 2
Output: 1

Example 2

Input: n = 4
Output: 3

Example 3

Input: n = 30
Output: 832040

Constraints

0 ≤ n ≤ 30

Pattern clues in the wording

→ Defined by a recurrence on smaller inputs
→ Overlapping subproblems (F(n − 2) is needed twice)

These clues point to Recursion: Solve the problem by solving a smaller version of it, with a base case that stops the calls.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int fib(int n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 2	1
2	n = 4	3
3	n = 0	0

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Plain recursion · O(2ⁿ)2. Memoised recursion · O(n)3. Optimal: two variables · O(n)

Plain recursion

Time O(2ⁿ) Space O(n) stack

Translate the definition directly.

Approach 1

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }
}

Verdict: Correct and readable, but recomputes the same values exponentially often.

Memoised recursion

Time O(n) Space O(n)

Store each F(k) the first time it's computed and reuse it.

Approach 2

class Solution {
    private final int[] memo = new int[31];

    public int fib(int n) {
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fib(n - 1) + fib(n - 2);
    }
}

Verdict: Linear: each value is computed once.

Optimal: two variables

Time O(n) Space O(1)

Walk up from F(0) and F(1), keeping only the last two values.

▶ Dry run: Rolling two valuesn = 5

State(vars)

a = 0b = 1

Step 1/4Start with F(0) = 0 and F(1) = 1.

Approach 3

class Solution {
    public int fib(int n) {
        int a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            int next = a + b;
            a = b;
            b = next;
        }
        return a;
    }
}

Verdict: The best for this range of n.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 0
n = 1

Mistakes people make

Off-by-one in the loop (returning b instead of a, or looping n − 1 times).

Interview

Follow-up questions

How could you compute F(n) for n around 10¹⁸ (modulo a number)?

Command Palette