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, Python, C++ and JavaScript, 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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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).
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.
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).