Recursive Logic

Thinking in Circles

You already know how to write functions in C. You call a function, it runs, and it returns. But what if a function called itself? This isn't a mistake; it's a powerful problem-solving technique called recursion. Instead of using a loop to repeat an action, we can have a function call itself to work on a smaller piece of the same problem.

Recursion works by breaking a problem down into two parts: a base case that can be solved directly, and a recursive step that simplifies the problem and calls the function again.

Think of it like opening a set of Russian nesting dolls. Your goal is to find the smallest doll. You open one doll (the recursive step) to find a slightly smaller one inside. You keep doing this until you open a doll and find it's solid (the base case). Once you hit the base case, the problem is solved.

The Call Stack in Action

When you call any function, the computer sets aside a chunk of memory for it on something called the call stack. This memory block, or , holds the function's parameters, local variables, and the address to return to when it's done. When the function finishes, its stack frame is removed.

With recursion, every time a function calls itself, a new stack frame is pushed onto the top of the stack. This continues until a call finally hits the base case. Then, the process reverses. Each function completes its task, and its stack frame is popped off the stack, one by one, until the stack is empty again.

#include <stdio.h>

// A recursive function to calculate factorial
int factorial(int n) {
    // Base case: if n is 0 or 1, factorial is 1
    if (n <= 1) {
        return 1;
    }
    // Recursive step: n * factorial of (n-1)
    else {
        return n * factorial(n - 1);
    }
}

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

In this factorial example, factorial(4) calls factorial(3), which calls factorial(2), and so on, until factorial(1) is called. This is the base case. It returns 1. Then factorial(2) can return 2 * 1. Then factorial(3) can return 3 * 2, and finally factorial(4) returns 4 * 6, giving the final answer of 24. Each of these calls had its own stack frame.

Head vs. Tail Recursion

The structure of a recursive function matters. The main distinction is between head and tail recursion, which depends on when the recursive call is made.

Head Recursion: The recursive call is made first, and the result is used in computations afterwards. Our factorial example used head recursion because the multiplication n * ... happens after the recursive call factorial(n - 1) returns a value.

Tail Recursion: The recursive call is the very last operation. There is no pending calculation to be done after the call returns. To achieve this, the result is usually passed along as a parameter.

#include <stdio.h>

// A tail-recursive function for factorial
int factorial_tail(int n, int accumulator) {
    // Base case
    if (n <= 1) {
        return accumulator;
    }
    // Recursive step: the last thing this function does is call itself
    else {
        return factorial_tail(n - 1, n * accumulator);
    }
}

int main() {
    int num = 4;
    // Initial call passes 1 as the starting accumulator
    printf("Factorial of %d is %d\n", num, factorial_tail(num, 1)); // Output: Factorial of 4 is 24
    return 0;
}

Why does this matter? Many compilers can perform (TCO). When a function is tail-recursive, the compiler can reuse the current stack frame for the next recursive call instead of creating a new one. This makes the recursive function just as memory-efficient as a standard loop. However, not all C compilers are guaranteed to perform this optimisation.

The Cost of Recursion

Recursion can lead to clean, readable code, especially for problems that are naturally recursive, like traversing tree or graph data structures. But this elegance comes at a cost. Each function call consumes memory and adds a small amount of processing overhead. For very deep recursion, this can be significant.

The biggest danger is . The call stack is finite. If a recursive function calls itself too many times—either because the problem is huge or because the base case is never reached—it will run out of stack memory and the program will crash. This is why a well-defined base case isn't just good practice; it's essential for a functioning recursive program.

If you don’t have a terminating case for the recursive example above, the stack will continue to grow in size adding additional stack frames on-top of each other, moving the stack pointer upward on each call, against the heap, which will be explained in the next section.

For many problems, an iterative solution using a loop is more memory-efficient and faster in C. However, for complex data structures like trees and graphs, a recursive approach often simplifies the logic so much that it's the preferred method. Understanding the mechanics of recursion allows you to make an informed choice between the two.

Now, let's test your understanding of how recursion works behind the scenes.

Quiz Questions 1/6

What is the defining characteristic of a recursive function in C?

Quiz Questions 2/6

What is the primary purpose of the "base case" in a recursive function?

Data Structures Foundations and Recursion