DSA SheetEasy
EditorialPractice

RECURSION & BACKTRACKING › RECURSION PROBLEMS

Fibonacci Number

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe recurrence only needs its two most recent values

The definition of Fibonacci gives you exactly what each new answer needs: F(n) is the sum of F(n - 1) and F(n - 2). Once you know two consecutive values, every later value can be produced from them. You do not need to keep the whole sequence because older values will never be used again.

Start with the known pair F(0) = 0 and F(1) = 1. For each index from 2 through n, add the pair to get the next value, then shift the pair forward. The base cases are handled before the loop, so the loop only performs the recurrence for values that are not already known.

Approach

  1. Return n immediately when n is 0 or 1, because those are the two values defined directly and the loop starts at index 2.
  2. Store F(0) in a and F(1) in b, because these are the two consecutive values needed to calculate the first new Fibonacci number.
  3. Loop i from 2 through n inclusive, because F(n) must be calculated and every index before it has already been represented by the moving pair.
  4. Compute c = a + b before changing either old value, because both previous values are required for the recurrence.
  5. Move a to b and b to c, because the pair must now represent F(i - 1) and F(i) for the next iteration.
  6. Return b after the loop, because at that point b holds F(n); returning a would return the preceding Fibonacci number instead.

Complexitythe loop reuses its working state

MEASUREBOUNDWHY
TimeO(n)The loop computes one new Fibonacci value for each index from 2 through n, and each iteration performs constant work, so no index is processed more than once.
SpaceO(1) extraOnly a, b, c, and the loop index are stored. The returned integer is required output and is excluded from the extra-space bound; the bound does not degrade for any allowed input shape because the input is a single integer.
Here n is the requested Fibonacci index.

Annotated solutionC++ · iterative · constant extra space

CPPIteratively compute Fibonacci values while retaining only the previous two values.
#include <vector>
using namespace std;

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;

        int a = 0;
        int b = 1;
        for (int i = 2; i <= n; ++i) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

The temporary c is essential. If you assign a = b before calculating the sum, you destroy one of the two values that the recurrence needs. After c is saved, the assignments shift the window from F(i - 2), F(i - 1) to F(i - 1), F(i), making the same three lines valid on the next iteration.

The memoized recursive alternativea direct recurrence at the cost of O(n) extra space

A recursive solution mirrors the definition: fib(n) asks for fib(n - 1) and fib(n - 2), then adds them. Plain recursion repeats the same subproblems many times, such as fib(n - 2) being reached through both branches. Memoization stores each computed value, so every argument from 0 through n is solved once.

CPPMemoized recursion follows the mathematical recurrence without solving the same index twice.
#include <vector>
using namespace std;

class Solution {
    vector<int> memo;

    int solve(int n) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];

        memo[n] = solve(n - 1) + solve(n - 2);
        return memo[n];
    }

public:
    int fib(int n) {
        memo.assign(n + 1, -1);
        return solve(n);
    }
};

Memoized recursion is an alternative arrangement, not an optimisation for this problem: it uses O(n) extra space for the memoization array and recursion stack, while the loop uses O(1). It buys a close match to the statement's recursive definition, which can make the relationship easier to see, but the iterative version is the better choice when space matters.

Common mistakestwo wrong shapes that change the recurrence or its cost

Previous · Power of Four