Recursion

Recursion is a powerful programming technique where a function calls itself, either directly or indirectly, to solve a problem. A recursive solution breaks a problem down into smaller, simpler subproblems that are identical in nature to the original problem. This process continues until the problem becomes so simple that it can be solved directly. Every recursive function must have two key components. The first is the **base case**: a condition under which the function does not call itself and instead returns a direct result. The base case is crucial because it prevents the recursion from continuing infinitely, which would lead to a stack overflow error. The second component is the **recursive step**: the part of the function that calls itself, but with modified arguments that move it closer to the base case. A classic example of recursion is calculating the factorial of a number. The factorial of n (n!) is the product of all positive integers up to n. This can be defined recursively: `factorial(n) = n * factorial(n-1)`, with the base case `factorial(0) = 1`. When a function is called, its state (local variables, parameters) is pushed onto the program's call stack. In recursion, each recursive call adds a new frame to the stack. When the base case is reached, the functions start returning, and the frames are popped off the stack one by one. While elegant, recursion can be less efficient than iterative solutions due to the overhead of function calls.