Scale Engineer

Fibonacci Number

Easy
#0496Time: O(2^n). For each call to `fib(n)`, we make two more calls, leading to a call tree that grows exponentially. This is very slow.Space: O(n). The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.10 companies
Patterns
MathRecursionDynamic ProgrammingMemoization
Companies
AccentureCapgeminiCognizantEY

Prompt

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

 

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

 

Constraints:

  • 0 <= n <= 30

Approaches

4 approaches with complexity analysis and trade-offs.

This approach directly translates the mathematical definition of the Fibonacci sequence, F(n) = F(n - 1) + F(n - 2), into a recursive function. The function calls itself for n-1 and n-2 and returns their sum. The base cases are F(0) = 0 and F(1) = 1.

Algorithm

  • Base Case: If n is 0 or 1, return n.
  • Recursive Step: Otherwise, return fib(n - 1) + fib(n - 2).

Walkthrough

The algorithm follows the recurrence relation F(n) = F(n-1) + F(n-2). We define a function fib(n). If n is 0 or 1, we return n as these are the base cases. Otherwise, we make two recursive calls: fib(n-1) and fib(n-2) and return their sum. This method is simple to understand but highly inefficient because it recomputes the same Fibonacci numbers multiple times. For example, to calculate fib(5), both fib(4) and fib(3) are called. fib(4) in turn calls fib(3) and fib(2). The value of fib(3) is computed twice, leading to an exponential number of calls.

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

Complexity

Time

O(2^n). For each call to `fib(n)`, we make two more calls, leading to a call tree that grows exponentially. This is very slow.

Space

O(n). The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.

Trade-offs

Pros

  • Very simple to write and understand.

  • Directly mirrors the mathematical formula.

Cons

  • Extremely inefficient due to redundant computations.

  • Will result in a 'Time Limit Exceeded' error for n greater than around 40.

Solutions

class Solution {public  int fib(int n) {    int a = 0, b = 1;    while (n-- > 0) {      int c = a + b;      a = b;      b = c;    }    return a;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem