Recursion & Memory Stack

Recursion is a programming technique where a function calls itself, directly or indirectly, to solve a problem. It breaks down complex mathematical or logical problems into smaller, identical sub-problems.

1. The Anatomy of Recursion

Every recursive function must have two components: - Base Case: The condition that terminates the recursion. Without a base case, the function will call itself infinitely, causing the program to run out of stack memory and crash. - Recursive Step: The logic where the function calls itself with a modified, smaller argument, moving closer to the base case.

Example: Calculating Factorial ($n!$)

The mathematical definition of factorial is: - $0! = 1$ (Base case) - $n! = n \times (n-1)!$ (Recursive step)

#include <stdio.h>

int factorial(int n) {
    // 1. Base Case
    if (n == 0 || n == 1) {
        return 1;
    }
    // 2. Recursive Step
    return n * factorial(n - 1);
}

int main() {
    int result = factorial(5);
    printf("Factorial of 5 is %d\n", result); // Output: 120
    return 0;
}

2. Call Stack & Stack Frames

When a function is called, the OS allocates a block of memory called a stack frame to store its parameters, return address, and local variables. For factorial(3), the stack builds up like this: 1. factorial(3) calls factorial(2) $ ightarrow$ Stack frame 1 2. factorial(2) calls factorial(1) $ ightarrow$ Stack frame 2 3. factorial(1) returns 1 (Base case) $ ightarrow$ Stack frame 3 is popped 4. factorial(2) calculates 2 * 1 = 2 $ ightarrow$ Stack frame 2 is popped 5. factorial(3) calculates 3 * 2 = 6 $ ightarrow$ Stack frame 1 is popped

[!CAUTION] Stack Overflow: If your recursion is too deep (e.g. lacks a base case, or has too many iterations), it will exceed the allocated size of the call stack, crashing your program instantly with a Segmentation Fault.

3. Recursion vs. Iteration

• Recursion: Cleaner code, easier for mathematical structures (trees, graphs), but has high memory overhead (due to multiple stack frames) and is slower.
• Iteration (Loops): More code, but highly memory-efficient (uses $O(1)$ memory space) and compiles faster.