Recursion vs Iteration

Recursion — a function calling itself — is often the most natural way to express problems that are themselves recursively structured: traversing a tree, computing a factorial, or implementing divide-and-conquer algorithms like quicksort. But C makes no special accommodation for recursion the way some languages do, and understanding its real costs is essential before reaching for it.

The Cost of Recursion in C

Every call pushes a new stack frame -- return address, parameters, and local variables -- consuming real, limited stack memory
C compilers are not required to perform tail-call optimization, and most do not reliably apply it even when a function is technically written in tail-recursive form
Deep or unbounded recursion can exhaust the call stack, causing a stack overflow -- a crash with no graceful recovery in standard C
Each call carries real function-call overhead (pushing arguments, jumping, returning) that a loop does not pay

Stack overflow is a real, common failure mode

Unlike a `NULL` pointer or an array bounds error, a stack overflow from unbounded recursion usually crashes the whole process immediately (a segmentation fault), often with no useful error message. It is easy to trigger accidentally with recursive functions that lack a correct base case, or that process input large enough to exceed a stack of just a few megabytes.

A Recursive Function

// Recursive: elegant, but one stack frame per element.
int sum_recursive(int *arr, int n) {
    if (n == 0) {
        return 0;
    }
    return arr[0] + sum_recursive(arr + 1, n - 1);
}

For a large array, this pushes one stack frame per element — summing a million-element array this way risks overflowing the stack on many systems, even though the logic itself is perfectly correct.

Converting to Iteration

The simplest fix, when possible, is to rewrite the recursive structure as a plain loop with an accumulator — no stack growth at all, regardless of input size:

// Iterative: same result, constant stack usage.
int sum_iterative(int *arr, int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

Not every recursive function is this easy to flatten. When the recursive structure genuinely needs to track multiple pending "branches" (like a tree traversal or backtracking search), you can convert it to iteration by maintaining an explicit stack data structure on the heap instead of relying on the call stack:

// Recursive tree traversal (in-order print), for comparison:
void print_inorder_recursive(struct node *root) {
    if (root == NULL) return;
    print_inorder_recursive(root->left);
    printf("%d ", root->value);
    print_inorder_recursive(root->right);
}

// Same traversal, iterative, using an explicit stack of node pointers.
void print_inorder_iterative(struct node *root) {
    struct node *stack[MAX_DEPTH];
    int top = -1;
    struct node *current = root;

    while (current != NULL || top >= 0) {
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }
        current = stack[top--];
        printf("%d ", current->value);
        current = current->right;
    }
}

The explicit-stack version does the same work but stores pending "come back to this node" state in an array you control (sized to a known bound, or heap-allocated and grown dynamically) rather than in call frames you do not control.

When to Prefer Each

Situation	Prefer
Input size is small and bounded (e.g. a fixed-depth tree)	Recursion -- clearer, matches the problem structure
Input size is large, unbounded, or attacker-controlled	Iteration -- avoids stack overflow risk entirely
The algorithm is naturally divide-and-conquer (quicksort, mergesort)	Recursion -- the recursive structure is the algorithm
Performance-critical hot loop	Iteration -- avoids per-call overhead, easier for the compiler to optimize
Simple linear accumulation (sums, counts, searches)	Iteration -- a loop expresses the same logic with O(1) stack usage

Do not rely on tail-call optimization in C

Some languages guarantee that a function whose last action is a recursive call reuses the current stack frame instead of growing the stack. The C standard makes no such guarantee, and most C compilers, even at high optimization levels, only apply this transformation opportunistically. Never write deeply-recursive C code assuming the compiler will "fix" the stack growth for you -- verify with your specific compiler and flags, or rewrite as a loop.