Problem Statement

Write a program that generates the Fibonacci series up to a given limit using recursion.

Problem Understanding

To solve this problem recursively, we need to understand that the Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones. Recursion involves breaking down a problem into smaller instances until reaching a base case. In this case, the base case occurs when the current number exceeds the limit specified by the user.

Examples

Example 1:

Input: 7
Output: 0 1 1 2 3 5 8 13 is the fibonacci series up to 7th term. (0 based indexing).

Example 2:

Input: 2
Output: 0 1 1 is the fibonacci series up to 2nd term. (0 based indexing).

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.

Code Implementation in C++

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