🌀 Fibonacci Series & Multiple Recursion Calls (Hinglish Explanation)

Fibonacci series ek classic recursion example hai jisme multiple recursive calls hoti hain har ek function ke andar.

🔢 Fibonacci Series Definition

Fibonacci series:

0, 1, 1, 2, 3, 5, 8, 13, ...

Each number is the sum of the previous two numbers.

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)  // for n >= 2

✅ Recursive Code (C++)

#include<iostream>
using namespace std;

int fibonacci(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;

    return fibonacci(n - 1) + fibonacci(n - 2);  // 🔁 Multiple Calls
}

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

🧾 Output: Fibonacci(5) = 5

🔁 Dry Run of fibonacci(4)

f(4)
├── f(3)
│   ├── f(2)
│   │   ├── f(1) → 1
│   │   └── f(0) → 0
│   └── f(1) → 1
├── f(2)
│   ├── f(1) → 1
│   └── f(0) → 0

🧠 Final Value:

f(4) = f(3) + f(2)
     = (f(2)+f(1)) + (f(1)+f(0))
     = (1+1) + (1+0)
     = 2 + 1 = 3

❗ Multiple Recursive Calls:

Each call spawns two more calls, so total calls grow exponentially.

🔥 Time Complexity:

T(n) = T(n-1) + T(n-2)
⇒ O(2^n)  ➤ Very Slow!