Recursion in C++

Recursion is a programming technique where a function calls itself either directly or indirectly to solve a problem. Each recursive call works on a smaller subproblem until it reaches a base condition that stops further calls.

Recursion is useful for solving problems that can be broken down into similar subproblems, such as factorial calculation, Fibonacci series, and tree traversals.

🔹 Types of Recursion

Direct Recursion – A function calls itself directly.
Indirect Recursion – A function calls another function which in turn calls the original function.

🔹 Basic Structure of a Recursive Function

returnType functionName(parameters) {
    if (base_condition) {
        // stop recursion
        return value;
    } else {
        // recursive call
        return functionName(smaller_problem);
    }
}

🔹 Example: Factorial Using Recursion

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1; // base condition
    else
        return n * factorial(n - 1); // recursive call
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num) << endl;
    return 0;
}

Output:

Factorial of 5 is 120

🔹 Example: Fibonacci Series Using Recursion

#include <iostream>
using namespace std;

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

int main() {
    int terms = 6;
    for (int i = 0; i < terms; i++) {
        cout << fibonacci(i) << " ";
    }
    return 0;
}

Output:

0 1 1 2 3 5

Important Notes

Every recursion must have a base condition to stop the recursion.
Without a base condition, it leads to infinite recursion and stack overflow errors.
Recursive calls consume more memory than iterative approaches.

Best Practices

Use recursion for problems that have a natural recursive structure.
For performance-critical code, prefer iteration to reduce overhead.
Use tail recursion if supported by compiler optimizations.