Fibonacci using Recursion

#include <iostream>
using namespace std;

// Recursive function to calculate Fibonacci number
int fibonacci(int n) {
    // Base cases
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int terms;
    cout << "Enter number of terms: ";
    cin >> terms;
    
    if (terms < 0) {
        cout << "Invalid input." << endl;
        return 1;
    }
    
    cout << "Fibonacci series:" << endl;
    for (int i = 0; i < terms; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    
    // Show individual Fibonacci numbers
    cout << "\nIndividual Fibonacci numbers:" << endl;
    for (int i = 0; i <= 10; i++) {
        cout << "F(" << i << ") = " << fibonacci(i) << endl;
    }
    
    return 0;
}

Enter number of terms: 10
Fibonacci series:
0 1 1 2 3 5 8 13 21 34

Individual Fibonacci numbers:
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

This program teaches you how to calculate Fibonacci Series using Recursion in C++. The Fibonacci sequence is one of the most famous sequences in mathematics, where each number is the sum of the two preceding numbers. Recursive implementation demonstrates the elegance of recursion, though it has performance limitations.

---

1. What This Program Does

The program demonstrates recursive Fibonacci calculation:

• Recursive function with multiple base cases
• Calculating Fibonacci numbers
• Generating Fibonacci series
• Understanding recursive structure

Recursion provides intuitive solution for Fibonacci sequence.

---

2. Header Files Used

1. #include <iostream>
   • Provides cout and cin for input/output operations.

---

3. Understanding Fibonacci Sequence

Fibonacci Definition:

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

Sequence:

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
• Each number = sum of previous two
• Appears in nature, mathematics, art

---

4. Multiple Base Cases

Base Cases:

if (n == 0) { return 0; } if (n == 1) { return 1; }

How it works:

• Two base cases needed
• F(0) = 0, F(1) = 1
• Stops recursion
• Returns known values

---

5. Recursive Case

Function Calls Itself:

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

How it works:

• Calls fibonacci(n-1) and fibonacci(n-2)
• Adds results together
• Reduces problem to smaller subproblems
• Builds solution from base cases

---

6. Recursion Flow

Example: fibonacci(5):

1. fibonacci(5) = fibonacci(4) + fibonacci(3)
2. fibonacci(4) = fibonacci(3) + fibonacci(2)
3. fibonacci(3) = fibonacci(2) + fibonacci(1)
4. fibonacci(2) = fibonacci(1) + fibonacci(0)
5. Base cases return: F(1)=1, F(0)=0
6. Results propagate back: F(2)=1, F(3)=2, F(4)=3, F(5)=5

---

7. Performance Consideration

Time Complexity:

• O(2^n) - exponential
• Repeated calculations
• Same values calculated multiple times
• Inefficient for large n

Optimization:

• Memoization: cache results
• Iterative: O(n) time
• Dynamic programming: store computed values
• Better for large n

---

8. When to Use Recursive Fibonacci

Best For:

• Learning recursion
• Small values of n
• Understanding recursive structure
• Educational purposes

Not Recommended For:

• Large values of n
• Performance-critical code
• Production applications
• Real-time systems

---

9. Important Considerations

Base Cases:

• Must have both F(0) and F(1)
• Stops recursion properly
• Prevents infinite recursion
• Essential for correctness

Stack Overflow:

• Deep recursion uses stack
• May overflow for large n
• Consider iterative approach
• Limited by stack size

Repeated Calculations:

• Same values calculated multiple times
• Inefficient recursive tree
• Memoization improves performance
• Trade-off: simplicity vs efficiency

---

10. return 0;

This ends the program successfully.

---

Summary

• Fibonacci: F(n) = F(n-1) + F(n-2), base cases: F(0) = 0, F(1) = 1.
• Recursive implementation: intuitive but inefficient (O(2^n)) due to repeated calculations.
• Multiple base cases needed: F(0) and F(1) stop recursion.
• Memoization or iterative approach better for large n.
• Understanding recursive Fibonacci demonstrates recursive thinking.
• Essential for learning recursion, though not optimal for performance.

This program is fundamental for learning recursion, understanding the Fibonacci sequence, and preparing for optimization techniques like memoization in C++ programs.