Start practising

Fibonacci Number (Recursion & Backtracking)

Easy Recursion & Backtracking Basic Recursion Original on LeetCode

Fibonacci Number is a easy recursion & backtracking problem solved with the basic recursion pattern. The best approach, optimal (memoised recursion), runs in O(n) time and O(n) space. Below are 2 approaches in Java, from plain recursion up.

Problem

The Fibonacci sequence starts F(0) = 0, F(1) = 1, and every later term is the sum of the previous two. Given n, return F(n).

In this module, focus on the recursion tree: why the plain version is exponential and how memoisation fixes it.

Examples

Example 1

Input
n = 6
Output
8
Why
0, 1, 1, 2, 3, 5, 8.

Example 2

Input
n = 1
Output
1

Constraints

  • 0 <= n <= 30

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Plain recursionO(2ⁿ)O(n)
Optimal (memoised recursion)O(n)O(n)

1Plain recursion

TimeO(2ⁿ)The call tree roughly doubles at each level.
SpaceO(n)Maximum recursion depth is n.

Translate the definition directly: fib(n) = fib(n - 1) + fib(n - 2). Correct, but the call tree branches twice at every level and recomputes the same values.

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

2Optimal (memoised recursion)

TimeO(n)
SpaceO(n)

Cache each fib(i) the first time it is computed. Every value is then computed once, which turns the exponential tree into a straight line. This is the bridge from recursion to dynamic programming.

  1. memo array filled with -1.
  2. If memo[n] is set, return it; otherwise compute, store and return.
Java
class Solution {
    private int[] memo;

    public int fib(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return go(n);
    }

    private int go(int n) {
        if (n < 2) return n;
        if (memo[n] != -1) return memo[n];
        return memo[n] = go(n - 1) + go(n - 2);
    }
}

Edge cases to test

  • n = 0 and n = 1 (both base cases)

Hints

Hint 1

Draw the call tree for fib(5). How many times is fib(2) computed?

FAQ

What is the best time complexity for Fibonacci Number?

Optimal (memoised recursion) runs in O(n) time and O(n) extra space.

Which pattern does Fibonacci Number use?

It is a recursion & backtracking problem that uses the basic recursion pattern. Other problems with the same pattern: Factorial of a number, Binary Tree Inorder Traversal (Recursive), Basic Backtracking Template.

Is there a brute force solution for Fibonacci Number?

Yes. Plain recursion takes O(2ⁿ) time and O(n) space. Translate the definition directly: fib(n) = fib(n - 1) + fib(n - 2).

Which edge cases should I test for Fibonacci Number?

n = 0 and n = 1 (both base cases).