Principles of Recursion

Recursion follows a set of fundamental principles that help in solving complex problems by breaking them into smaller subproblems.

These principles ensure that recursive functions work correctly and efficiently.

1. Base Case (Stopping Condition)

Every recursive function must have a base case, which defines when the recursion should stop. Without a base case, the function will keep calling itself indefinitely, leading to a stack overflow error.

Example: Factorial of a Number

The factorial of n is defined as: n! = n × (n−1)!

With the base case: 0! = 1

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

If we don’t include if (n == 0) return 1;, the function will keep calling itself indefinitely, eventually causing a stack overflow.

2. Recursive Case (Problem Reduction)

In recursion, the function should call itself with a reduced version of the problem. This is known as the recursive case. The recursive case must be defined properly so that it reduces the complexity of the problem in each step.

Example: Fibonacci Sequence

The Fibonacci sequence is defined recursively as: F(n) = F(n−1) + F(n−2)

With base cases: F(0) = 0, F(1) = 1

int fibonacci(int n) {
    if (n == 0) return 0; // Base case
    if (n == 1) return 1; // Base case
    return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}

Without it, the function would not break the problem into smaller parts, making it impossible to compute the result recursively.

3. Progress Toward the Base Case (Convergence Property)

Each recursive call should move closer to the base case. If there is no progress toward the base case, the recursion will never terminate.

To ensure this, the function should reduce the problem size in each recursive call. If the reduction is not happening, the function might get stuck in an infinite loop.

Example: Incorrect vs. Correct Recursion

Correct Recursion:

#include <stdio.h>

void countdown(int n) {
    if (n == 0) {  // Base case
        printf("Blastoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);  // Moves toward base case
}

int main() {
    countdown(5);
    return 0;
}

Incorrect Recursion:

#include <stdio.h>

void countdown(int n) {
    if (n == 0) {  // Base case
        printf("Blastoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n);  // Incorrect: No progress toward base case
}

int main() {
    countdown(5);
    return 0;
}

In this incorrect example, the countdown function calls itself with the same value n each time (countdown(n)), so the value never decreases and the base case (n == 0) is never reached.

This results in infinite recursion and eventually causes a stack overflow error.

4. Stack Memory Usage (Call Stack)

Each recursive call is pushed onto the call stack, and execution resumes when a function returns its result. Too many recursive calls may overflow the stack.

Example: Recursive Calls in Factorial

For factorial(4), the function calls are:

#include <stdio.h>

int factorial(int n) {
    printf("Calling factorial(%d)\n", n); // Shows stack depth
    if (n == 0) return 1;
    int result = n * factorial(n - 1);
    printf("Returning factorial(%d) = %d\n", n, result);
    return result;
}

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

Output (shows stack behavior):

Calling factorial(4)
Calling factorial(3)
Calling factorial(2)
Calling factorial(1)
Calling factorial(0)
Returning factorial(1) = 1
Returning factorial(2) = 2
Returning factorial(3) = 6
Returning factorial(4) = 24
Factorial of 4 is 24

Now, results are returned as the stack unwinds:

After reaching the base case, the function starts returning values in reverse order.

4. Correctness by Mathematical Induction

Recursion follows the principle of mathematical induction, meaning:

1. Base Case Validity: If the base case is correct, it ensures correctness for small inputs.
2. Inductive Step: If recursion works for n−1, it must work for n.

Example: Sum of First N Natural Numbers

1. Base Case: sumN(0) = 0 is correct.
2. Inductive Step: Assume sumN(n-1) is correct, then sumN(n) = n + sumN(n-1) must also be correct.

By induction, the function works for all n ≥ 0.

#include <stdio.h>

int sumN(int n) {
    if (n == 0) return 0;  // Base case
    return n + sumN(n - 1);  // Recursive case
}

int main() {
    int n = 5;
    printf("Sum of first %d numbers is %d\n", n, sumN(n));
    return 0;
}

Recursion is a powerful tool, but it must be used correctly to avoid issues like infinite recursion, high memory usage, and performance inefficiencies.

By following these five core principles, you can write efficient and correct recursive functions.