Recursion in C Programming

Recursion is a programming technique where a function calls itself, either directly or indirectly, to solve a problem. In C, recursion provides an elegant way to solve complex problems by breaking them down into smaller, more manageable sub-problems of the same type.

A function that calls itself is known as a recursive function.

1. The Theory: How Recursion Works

The logic of recursion is based on the mathematical principle of mathematical induction. To prevent a function from calling itself infinitely, every recursive function must follow two fundamental rules:

A. The Base Case (Stopping Condition)

The base case is a specific condition where the function stops calling itself and returns a simple value. Without a base case, the function will enter an infinite recursion, eventually leading to a Stack Overflow error.

B. The Recursive Step (Recursive Case)

This is the part of the function where the "self-call" happens. Crucially, the arguments passed to the recursive call must be "smaller" or "closer" to the base case than the current arguments.

2. Memory Management: The Stack Frame

To understand recursion, one must understand the System Stack.

1. Each time a function is called, a new stack frame (activation record) is pushed onto the stack. This frame stores the function’s local variables, parameters, and the return address.

2. In recursion, these frames pile up as the function calls itself deeper and deeper.

3. Once the Base Case is reached, the function returns a value to the previous call.

4. The stack then begins to unwind, popping frames off one by one as each call completes its calculation until the final result is returned to main().

3. Practical Code Example: Factorial Calculation

The factorial of a number $n$ (written as $n!$) is defined as $n \times (n-1) \times (n-2) \dots \times 1$.

• Recursive Logic: $n! = n \times (n-1)!$

• Base Case: $0! = 1$

#include <stdio.h>

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

int main() {
    int num = 5;
    printf("Factorial of %d is %ld\n", num, factorial(num));
    return 0;
}

Execution Trace for factorial(3):

1. factorial(3) calls factorial(2) → (Wait for result: $3 \times ?$)

2. factorial(2) calls factorial(1) → (Wait for result: $2 \times ?$)

3. factorial(1) hits Base Case, returns 1.

4. factorial(2) receives 1, calculates $2 \times 1 = 2$, returns 2.

5. factorial(3) receives 2, calculates $3 \times 2 = 6$, returns 6.

4. Types of Recursion

5. Recursion vs. Iteration (Loops)