A Function Calling Itself

Recursion is a powerful (and sometimes mind-bending) technique where a function solves a problem by calling a smaller, simpler version of itself. It is the "Divide and Conquer" strategy in its purest form.

The Two Pillars of Recursion

Every recursive function must have these two parts, or it will fail:

1. The Base Case: The stopping condition. This is the simplest possible version of the problem that can be solved instantly. Without this, the function will call itself forever until the computer runs out of memory, causing a Stack Overflow crash.
2. The Recursive Step: The part where the function calls itself with a modified argument, slowly moving closer and closer to the base case.

Classic Example: The Factorial

Mathematical definition: n! = n (n-1) (n-2) ... 1 Recursive definition:

• fact(0) = 1 (Base Case)
• fact(n) = n * fact(n-1) (Recursive Step)

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1); // Recursive step
}

How it works in Memory (The Stack)

Each time a function calls itself, the computer adds a new Stack Frame to its RAM. This frame stores the local variables and the return address. When the base case is finally hit, the computer starts "unwinding" the stack, taking the results from the top frame and passing them back down until it reaches the original caller.

Recursion vs. Iteration (Loops)

• Recursion is often much more elegant and easier to read for problems involving trees, nested folders, or complex mathematical formulas (like Fibonacci).
• Iteration is usually faster and uses significantly less memory because it doesn't create new stack frames for every step.

When to use Recursion?

• Searching through a file system (Folders inside folders).
• Sorting algorithms like MergeSort and QuickSort.
• Mathematical sequences.
• Evaluating complex expressions (like in a calculator app).

Never use recursion for simple tasks like counting to 1,000,000. Each call takes up memory, and you will crash the program long before you reach the end. For simple repetition, a for loop is always better.