What is recursion?

Recursion is a method of defining a function, procedure, or data structure through itself. In the context of functions, recursion means that the function calls itself during its execution.

Main components of a recursive function:

1. Base case: The condition under which recursion stops. Without a base case, recursion would be infinite.
2. Recursive step: The step where the function makes a recursive call to itself, but with modified arguments that bring the execution closer to the base case.

Example of recursive factorial calculation:

#include <iostream>

long long factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n <= 1) {
        return 1;
    }
    // Recursive step: n! = n * (n-1)!
    return n * factorial(n - 1);
}

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

Recursion is often used to solve problems that are easily expressed in terms of simpler subproblems of the same type, such as traversing data structures (trees, graphs), sorting (e.g., Merge Sort, Quick Sort), or computing mathematical functions (e.g., Fibonacci numbers, factorial).

Important points:

• Each recursive call creates a new stack frame. Excessive recursive calls can lead to stack overflow.
• Recursive solutions can often be transformed into iterative ones (using loops and explicit stacks), and vice versa. Iterative solutions are generally more memory-efficient but may be less clear and readable for some problems.
• Tail recursion optimization, if supported by the compiler, allows avoiding stack growth for certain types of recursive calls.