C++ Recursion Example

Recursion is a programming concept where a function calls itself in order to solve a problem. Recursive functions have two main components: a base case that defines the simplest possible scenario and a recursive case that breaks down a larger problem into smaller, similar subproblems. Recursive solutions are often elegant and can be used to solve a wide range of problems.

Example: Factorial Calculation

#include <iostream>

// Recursive function to calculate factorial
unsigned long long factorial(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return 1;
    }
    // Recursive case
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    // Function call
    int result = factorial(5);

    // Display the result
    std::cout << "Factorial: " << result << std::endl;

    return 0;
}

In this example, the factorial function calculates the factorial of a number n. The base case is when n is 0 or 1, where the factorial is 1. The recursive case multiplies n by the factorial of n - 1. The function calls itself until it reaches the base case.

Key Elements of Recursion:

1. Base Case: A condition that indicates when the recursion should stop. It defines the simplest scenario that doesn't require further recursion.
2. Recursive Case: A condition that defines how the problem can be broken down into smaller, similar subproblems. The function calls itself with a modified input.
3. Termination: The recursion must eventually reach the base case to avoid an infinite loop.

Recursion is often used in solving problems where a task can be broken down into smaller instances of the same task. Examples include tree traversal, sorting algorithms (e.g., quicksort), and mathematical problems (e.g., Fibonacci sequence).

However, it's essential to use recursion judiciously, as it can lead to stack overflow errors for deep recursive calls. For some problems, an iterative approach might be more efficient or easier to understand.