Nth Fibonacci number with recursion

"Write a recursive function to compute the nth Fibonacci number." It's probably the most common recursion question in all of programming education, and for good reason. This problem, also known as Fibonacci Number on LeetCode, strips recursion down to its essence: a base case and a recurrence relation. If you can solve this cleanly, you understand the building blocks that power every recursive algorithm.

TL;DR

Return n directly when n is 0 or 1 (the base cases). Otherwise, return fibonacci(n-1) + fibonacci(n-2). That's the entire solution. Two lines of logic. The catch is that this naive approach runs in O(2^n) time because it recomputes the same subproblems repeatedly, but this problem specifically asks for the recursive implementation.

Why This Problem Matters

Fibonacci with recursion is your gateway to understanding three critical concepts: base cases, recurrence relations, and the cost of redundant computation. Once you see why naive recursion is slow here, you'll naturally understand why memoization and dynamic programming exist. Every DP problem is, at its core, a recursion that got optimized.

The Fibonacci Sequence

The sequence starts with 0 and 1. Each subsequent number is the sum of the two before it:

The mathematical definition is straightforward:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2) for n > 1

This definition is already recursive. Our implementation will mirror it directly.

Understanding the Problem

Given a zero-indexed integer n (where n < 15), return the nth Fibonacci number.

fibonacci(0) -> 0
fibonacci(1) -> 1
fibonacci(3) -> 2
fibonacci(5) -> 5
fibonacci(8) -> 21

Edge Cases

1. n = 0: Return 0 (first element of the sequence)
2. n = 1: Return 1 (second element)
3. Small n constraint: Since n < 15, the exponential time complexity won't cause issues in practice

Solution Approach

The recursive definition translates almost word-for-word into code. But first, let's visualize what happens when we call fibonacci(4):

Notice how fib(2) is computed twice and fib(1) is computed three times. This redundancy is the hallmark of the naive recursive approach. For fibonacci(4) it's tolerable, but for fibonacci(40) it would make billions of redundant calls.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int fibonacci(int n) {
    // Base case: fib(0) = 0, fib(1) = 1
    if (n <= 1) {
      return n;
    }

    // Recursive case: fib(n) = fib(n-1) + fib(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

The elegance here is that the code reads like the mathematical definition:

1. Base case: When n is 0 or 1, return n itself. This is clean because fib(0) = 0 and fib(1) = 1, which are exactly the values of n.
2. Recursive case: Add the two preceding Fibonacci numbers. The recursion unwinds until it hits base cases, then the results bubble back up through the call stack.

Complexity Analysis

Time: O(2^n). Each call spawns two more calls, creating a binary tree of depth n. The total number of calls is roughly 2^n. For n = 14 (our maximum), that's about 16,000 calls, which is fine. For n = 50, it would be over a quadrillion.

Space: O(n). The call stack grows to a maximum depth of n. Even though the tree is wide, only one branch is active at a time. The deepest chain is fib(n) -> fib(n-1) -> fib(n-2) -> ... -> fib(0), which is n frames deep.

Why So Slow?

The recursion tree shows the problem clearly. To compute fib(5):

• fib(3) is computed 2 times
• fib(2) is computed 3 times
• fib(1) is computed 5 times
• fib(0) is computed 3 times

Each of those redundant computations fans out into its own subtree of redundant work. The fix is memoization or bottom-up DP, which reduces the time to O(n) by storing results of subproblems. But that's a problem for another day.

Common Pitfalls

1. Missing a base case: If you only handle n == 0, then fibonacci(1) will call fibonacci(0) + fibonacci(-1), leading to infinite recursion. Always handle both n == 0 and n == 1.

2. Off-by-one indexing: The sequence is 0-indexed. fibonacci(0) returns 0, not 1. Double check with the examples.

3. Trying to optimize prematurely: This problem asks for recursion specifically. Don't add memoization unless asked. Show that you can write clean recursive code first.

Interview Tips

When presenting this solution:

• Write the base case and recursive case clearly. Name them explicitly: "This is my base case, this is my recurrence."
• Draw the recursion tree for a small input like fib(4). Point out the redundant computations.
• Mention that you know this is O(2^n) and that memoization would fix it. This signals depth of understanding.
• If the interviewer asks for optimization, you're already set up to add a cache or switch to iteration.

Key Takeaways

• Recursive Fibonacci directly mirrors the mathematical definition: base cases fib(0)=0, fib(1)=1 and the recurrence fib(n) = fib(n-1) + fib(n-2).
• The naive recursive approach runs in O(2^n) time because it recomputes subproblems exponentially. For small n this is fine; for large n it's unusable.
• Space complexity is O(n) due to the maximum call stack depth, even though the recursion tree has exponentially many nodes.
• Understanding why this is slow is the first step toward dynamic programming. Memoization or bottom-up iteration both reduce the time to O(n).
• Always handle both base cases (n=0 and n=1). Missing one causes infinite recursion or incorrect results.

Practice and Related Problems

Once you've nailed recursive Fibonacci, try these natural progressions:

• Linear time Fibonacci (iterative approach with O(1) space)
• Climbing stairs (Fibonacci in disguise)
• House robber (DP with similar recurrence structure)

This problem and hundreds of others are available on Firecode, where spaced repetition ensures you internalize patterns like recursion and DP rather than just memorizing solutions. Building strong recursive thinking here pays dividends across your entire interview preparation.

Solutions in Other Languages

Python

class Solution:
    def fibonacci(self, n: int) -> int:
        if n <= 1:
            return n

        return self.fibonacci(n - 1) + self.fibonacci(n - 2)

JavaScript

class Solution {
  fibonacci(n) {
    if (n <= 1) {
      return n;
    }

    return this.fibonacci(n - 1) + this.fibonacci(n - 2);
  }
}

TypeScript

class Solution {
  fibonacci(n: number): number {
    if (n <= 1) {
      return n;
    }

    return this.fibonacci(n - 1) + this.fibonacci(n - 2);
  }
}

C++

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

    return fibonacci(n - 1) + fibonacci(n - 2);
  }
};

Go

package solution

func (s *Solution) Fibonacci(n int) int {
    if n <= 1 {
        return n
    }

    return s.Fibonacci(n-1) + s.Fibonacci(n-2)
}

Scala

class Solution {
  def fibonacci(n: Int): Int = {
    if (n <= 1) {
      n
    } else {
      fibonacci(n - 1) + fibonacci(n - 2)
    }
  }
}

Kotlin

class Solution {
    fun fibonacci(n: Int): Int {
        if (n <= 1) {
            return n
        }

        return fibonacci(n - 1) + fibonacci(n - 2)
    }
}

Swift

class Solution {
    func fibonacci(_ n: Int) -> Int {
        if n <= 1 {
            return n
        }

        return fibonacci(n - 1) + fibonacci(n - 2)
    }
}

Rust

impl Solution {
    pub fn fibonacci(&self, n: i32) -> i32 {
        if n <= 1 {
            return n;
        }

        self.fibonacci(n - 1) + self.fibonacci(n - 2)
    }
}

C#

public class Solution {
    public int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Dart

class Solution {
  int fibonacci(int n) {
    if (n <= 1) {
      return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

PHP

class Solution {
    public function fibonacci(int $n): int {
        if ($n <= 1) {
            return $n;
        }

        return $this->fibonacci($n - 1) + $this->fibonacci($n - 2);
    }
}

Ruby

class Solution
  def fibonacci(n)
    return n if n <= 1

    fibonacci(n - 1) + fibonacci(n - 2)
  end
end