C++ Recursion Basics

Recursion in C++ occurs when a function calls itself to solve a smaller instance of the same problem. It is commonly used in factorial, Fibonacci series, and tree traversals.

1. Recursion Syntax

A recursive function must have a base case to terminate the recursion and a recursive call that reduces the problem size.

return_type function_name(parameters) {
    if (base_condition) {
        // base case
        return value;
    } else {
        return function_name(smaller_problem); // recursive call
    }
}

2. Factorial Example

This example calculates the factorial of a number using recursion.

#include <iostream>
using namespace std;

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

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

3. Fibonacci Example

This example generates Fibonacci numbers using recursion.

#include <iostream>
using namespace std;

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

int main() {
    int n = 10;
    for (int i = 0; i < n; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    return 0;
}

4. Common Mistakes

Missing a base case, calling the function with incorrect parameters, or infinite recursion can cause runtime errors. Always ensure proper termination conditions.

Conclusion

C++ recursion is a powerful tool for solving problems by breaking them into smaller instances. Proper base cases and careful design prevent infinite recursion and stack overflow.