Fibonacci Number

Problem Statement

The Fibonacci numbers, commonly denoted as 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).

LeetCode:

509. Fibonacci Number

Examples

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

Theory

The fibonacci series is defined by the following recurrence relation:

F(n) = F(n-1) + F(n-2)

with base cases:

F(0) = 0
F(1) = 1

Each subsequent number in the Fibonacci series is the sum of the two preceding numbers.

Different Approaches

Simple Recursion (Naive):

Intuition:

This directly follows the definition:

• F(n) = F(n-1) + F(n-2)
• Use recursion to compute both subproblems

But – it recalculates many values again and again.

For example:

F(5)
├─ F(4)
│  ├─ F(3)
│  │  ├─ F(2)
│  │  ├─ F(1)
│  └─ F(2)
└─ F(3)

Notice F(2) and F(3) are computed multiple times.

Code:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 7;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

#include <iostream>

// Recursive function to generate Fibonacci series
void fibonacci(int limit, int a = 0, int b = 1) {
    // Base case: If the current number exceeds the limit
    if (a > limit) {
        return;
    }
    
    // Print the current number
    std::cout << a << " ";
    
    // Recursively call fibonacci with the next two numbers
    fibonacci(limit, b, a + b);
}

int main() {
    int limit;

    // Prompt the user to enter the limit
    std::cout << "Enter the limit for Fibonacci series: ";
    std::cin >> limit;

    // Generate and print the Fibonacci series
    std::cout << "Fibonacci series up to " << limit << ":\n";
    fibonacci(limit);

    return 0;
}

Complexity Analysis:

• Time Complexity:
  • O(2^N) — Each function call makes two more calls (for n-1 and n-2), resulting in an exponential growth in the number of calls.
• Space Complexity:
  • The space complexity of the solution is O(n) as well.