Recursion

What is Recursion?

Recursion is a programming technique where a function calls itself, directly or indirectly, to solve a problem. It works by breaking down a complex problem into smaller, more manageable sub-problems of the same type.

Think of it like nested Russian Dolls (Matryoshka): inside a large doll is a slightly smaller doll, which contains another smaller doll, until you reach the smallest doll that cannot be opened.

Anatomy of a Recursive Function

Every valid recursive function must have two essential components:

1. The Base Case (The Stop Condition)

The condition under which the function stops calling itself. Without a proper base case, the function will call itself infinitely, leading to a critical Stack Overflow error where the application runs out of stack memory.

2. The Recursive Case (The Step)

The part of the function where it makes the recursive call, passing a reduced or modified input that actively moves closer toward the base case condition.

void recursiveFunction(int input) {
    // 1. Base Case
    if (input <= 0) {
        return;
    }
    
    // 2. Recursive Case (with reduced input)
    recursiveFunction(input - 1);
}

Memory Layout: The Call Stack

When a function executes, the computer suspends the caller and creates an Activation Record (Stack Frame) on the Call Stack containing parameter arguments, local variables, and the return address.

• Winding Phase: Recursive calls are made, pushing new frames onto the Call Stack and allocating memory.
• Unwinding Phase: Once the base case is triggered, the functions return values, frames are popped off the Call Stack, and memory is reclaimed.

Recursion vs Iteration