Fibonacci Number

EASY

Description

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

Checkout 4 different approaches to solve Fibonacci Number. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Recursion

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

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 Analysis

Time Complexity: 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 Complexity: O(n). The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Fibonacci Number. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Fibonacci Number

Patterns:

MathRecursionDynamic ProgrammingMemoization

Companies:

Accenture |Capgemini |Cognizant |EY |