C++ Recursion

In C++, recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. Recursion provides an elegant way to break down complex problems into simpler subproblems and is commonly used in algorithms like factorial computation, Fibonacci sequence generation, and tree traversal.

1. Basic Recursion Example

Example of a factorial function using recursion:

#include <iostream>

// Function declaration
unsigned long long factorial(int n);

int main() {
    int num = 5;
    unsigned long long fact = factorial(num);

    std::cout << "Factorial of " << num << " = " << fact << std::endl;

    return 0;
}

// Function definition
unsigned long long factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

2. Fibonacci Sequence with Recursion

Example of generating Fibonacci sequence using recursion:

#include <iostream>

// Function declaration
unsigned long long fibonacci(int n);

int main() {
    int num = 10;

    std::cout << "Fibonacci sequence up to " << num << ":" << std::endl;
    for (int i = 0; i <= num; ++i) {
        std::cout << fibonacci(i) << " ";
    }
    std::cout << std::endl;

    return 0;
}

// Function definition
unsigned long long fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

3. Indirect Recursion

Example of indirect recursion:

#include <iostream>

// Function declarations
void funA(int n);
void funB(int n);

int main() {
    int num = 3;

    // Call function A, which will call function B
    funA(num);

    return 0;
}

// Function definition for funA
void funA(int n) {
    if (n > 0) {
        std::cout << "Function A: " << n << std::endl;
        funB(n - 1);
    }
}

// Function definition for funB
void funB(int n) {
    if (n > 1) {
        std::cout << "Function B: " << n << std::endl;
        funA(n / 2);
    }
}

Conclusion

Recursion in C++ provides a powerful technique for solving problems by breaking them down into simpler subproblems. This chapter covered basic recursion, examples with factorial and Fibonacci sequence, and indirect recursion. Understanding recursion allows you to implement efficient algorithms and solve complex programming challenges in C++.