Recursion

A recursive function invokes itself, directly or through other functions. Each call works on its own parameter and local objects, while all active calls share the function’s code. Recursion is useful when a problem or input is naturally defined in smaller versions of itself—but only when the base cases, progress, resource limits, and return relationships are explicit.

This chapter focuses on C execution and implementation discipline. Recurrence solving, divide-and-conquer design, backtracking, and algorithmic strategy belong to the Algorithms course.

Recursive Functions

The factorial function follows a mathematical recursive definition for non-negative integers:

0! = 1
n! = n × (n - 1)!  for n > 0

A direct C translation is:

unsigned long long factorial(unsigned int n) {
    if (n == 0U) {
        return 1ULL;
    }

    return n * factorial(n - 1U);
}

The code illustrates the form but lacks an overflow policy. On a common 64-bit unsigned long long, values beyond 20! wrap modulo the type’s range. A trustworthy interface either constrains n, reports overflow, or uses a representation capable of larger results.

Base Cases

A base case produces a result without another recursive call. It stops descent:

size_t string_length(const char *text) {
    if (*text == '\0') {
        return 0;
    }

    return 1 + string_length(text + 1);
}

This function requires a valid null-terminated string and one call per character. The base case is reached at the terminator.

A missing or unreachable base case causes calls to continue until a resource fails, usually by exhausting call-stack capacity. A base case must cover the smallest valid inputs and every valid recursive path must move toward one.

Multiple base cases can be appropriate:

unsigned long long fibonacci(unsigned int n) {
    if (n == 0U) {
        return 0ULL;
    }
    if (n == 1U) {
        return 1ULL;
    }

    return fibonacci(n - 1U) + fibonacci(n - 2U);
}

This is a clear definition but an inefficient implementation because it repeats calls extensively and still overflows eventually. It is a teaching example, not a recommendation for production Fibonacci computation.

Recursive Cases

A recursive case has two responsibilities:

1. reduce the current input toward a base case;
2. combine the smaller result into the current result.

For factorial, n - 1 is the progress step and multiplication combines results. For string length, text + 1 advances within the string and 1 + accounts for the current character.

State a variant that decreases: n for factorial or the number of characters remaining before \0 for string length. If the variant can stop decreasing because of overflow, invalid input, or a mistaken update, termination is not established.

Call Stack

Each active call needs an execution context containing parameters, automatic locals, a return location, and implementation bookkeeping. Implementations normally organise these contexts as stack frames.

For factorial(4):

factorial(4) waits for factorial(3)
  factorial(3) waits for factorial(2)
    factorial(2) waits for factorial(1)
      factorial(1) waits for factorial(0)
        factorial(0) returns 1
      returns 1 × 1 = 1
    returns 2 × 1 = 2
  returns 3 × 2 = 6
returns 4 × 6 = 24

Calls descend until a base result is available, then unwind in reverse order.

Automatic locals belong to individual invocations:

void countdown(unsigned int n) {
    unsigned int current = n;
    printf("%u\n", current);

    if (n > 0U) {
        countdown(n - 1U);
    }
}

Each active frame has a distinct current object even though the source declaration is written once.

Recursion Tracing

Trace both entry and return:

unsigned int triangular(unsigned int n) {
    if (n == 0U) {
        return 0U;
    }
    return n + triangular(n - 1U);
}

Trace tables expose two common misunderstandings: the caller does not disappear while the callee runs, and local variables in separate invocations are not one shared object.

Step through the call-stack experiment to compare the descent of five distinct frames with the reverse order in which their results return.

Direct Recursion

Direct recursion occurs when a function calls itself:

void print_reverse(const char *text) {
    if (*text == '\0') {
        return;
    }

    print_reverse(text + 1);
    putchar((unsigned char)*text);
}

The output happens during unwinding, so "cat" prints tac. The function assumes the input string is live and terminated for the entire recursion.

Moving putchar before the recursive call prints the original order. Position relative to the call controls whether work occurs during descent or ascent.

Indirect Recursion

Indirect recursion forms a cycle across functions:

static bool is_even(unsigned int n);
static bool is_odd(unsigned int n);

static bool is_even(unsigned int n) {
    return n == 0U ? true : is_odd(n - 1U);
}

static bool is_odd(unsigned int n) {
    return n == 0U ? false : is_even(n - 1U);
}

Each function needs a prior declaration because their definitions refer to one another. The shared variant n decreases across the call cycle.

Indirect recursion can model mutually defined states or grammars, but the termination argument is harder to see because no single function contains the whole cycle. Document the shared base cases and progress measure.

Tail Recursion

A call is in tail position when its result becomes the caller’s result without pending work:

static unsigned long long factorial_tail(unsigned int n,
                                         unsigned long long accumulator) {
    if (n == 0U) {
        return accumulator;
    }

    return factorial_tail(n - 1U, accumulator * n);
}

No multiplication waits after the recursive call; the multiplication happens while forming the next arguments.

C does not guarantee tail-call elimination. An optimizing compiler may reuse a frame, but portable correctness and resource planning must assume one active call per recursion level. Tail-recursive spelling is therefore not a portable solution to stack-depth risk.

The multiplication can overflow before the base case. Tail form changes pending work, not numeric limits.

Recursive Depth

Recursion depth is the maximum number of simultaneously active calls. For a linear recursion on n, depth is commonly proportional to n. For the string example, depth equals the length plus the base call.

C specifies no minimum supported recursion depth suitable for arbitrary user input. Available call-stack space depends on the implementation, environment, local-frame size, optimisation, and other factors.

Never use unbounded external input directly as recursion depth. Options include:

• impose and validate a documented maximum;
• convert to iteration;
• use explicit dynamically managed work storage;
• redesign to process incrementally.

Large automatic arrays inside a recursive function multiply per-frame storage and can exhaust resources quickly.

Stack Overflow

When recursion consumes more call-stack resources than available, C does not provide a standard, recoverable “stack overflow exception.” Behaviour is outside the portable language guarantees and often ends the process or corrupts state.

This function has no progress:

void forever(unsigned int n) {
    forever(n); /* same state; no reachable base case */
}

Even correct recursion can overflow on a valid but huge input. Logical termination and practical resource safety are separate obligations.

Iterative Conversion

Linear tail recursion usually maps directly to a loop:

bool factorial_checked(unsigned int n, unsigned long long *result) {
    if (result == NULL) {
        return false;
    }

    unsigned long long value = 1ULL;

    for (unsigned int factor = 2U; factor <= n; factor++) {
        if (value > ULLONG_MAX / factor) {
            return false;
        }
        value *= factor;
    }

    *result = value;
    return true;
}

The accumulator becomes a local variable, the recursive progress parameter becomes the loop variable, and the base case becomes the loop exit. The function also adds an overflow contract.

Explicit Work Storage

Not every recursion is tail recursion. When work must resume after processing a subproblem, conversion may require explicit saved state. An array or dynamically allocated stack can store pending states. That design belongs with the relevant data structure and algorithm; the key C insight is that removing recursive calls does not remove the need to remember unfinished work.

Choosing a Form

Prefer recursion when:

• the data or grammar is recursively shaped;
• the depth has a safe, known bound;
• the recursive contract is clearer than manual state management.

Prefer iteration when:

• progression is linear;
• input can make depth large or adversarial;
• stack resources are constrained;
• the iterative invariant is equally or more readable.

Side Effects During Recursion

Output or mutation can happen during descent or unwinding:

void show(unsigned int n) {
    if (n == 0U) {
        return;
    }

    printf("enter %u\n", n);
    show(n - 1U);
    printf("leave %u\n", n);
}

For show(3), output is:

enter 3
enter 2
enter 1
leave 1
leave 2
leave 3

This pattern helps trace resource acquisition before a recursive call and cleanup after it. Every acquired resource must still be released if deeper processing fails, so status propagation and cleanup contracts matter.

Palindrome Case

A half-open range makes recursive string reasoning explicit. [begin, end) contains the bytes at begin through end - 1; an empty range has begin == end.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static bool palindrome_range(const char text[],
                             size_t begin, size_t end) {
    if (end - begin < 2) {
        return true;
    }
    if (text[begin] != text[end - 1]) {
        return false;
    }
    return palindrome_range(text, begin + 1, end - 1);
}

static bool is_palindrome(const char text[]) {
    return palindrome_range(text, 0, strlen(text));
}

int main(void) {
    const char *samples[] = {"", "x", "level", "radar", "reader"};
    size_t count = sizeof samples / sizeof samples[0];

    for (size_t i = 0; i < count; i++) {
        printf("\"%s\": %s\n",
               samples[i],
               is_palindrome(samples[i]) ? "yes" : "no");
    }
    return EXIT_SUCCESS;
}

The wrapper establishes the internal preconditions:

text designates a null-terminated string
0 <= begin <= end <= strlen(text)

The recursive function may then subtract end - begin safely because begin <= end. It checks a range of length zero or one before computing end - 1, avoiding unsigned underflow on the empty string.

For "level", the calls descend like this:

For "reader", the first call compares r with r, then the second compares e with e, and the third compares a with d; false returns immediately through every waiting caller. No later pairs are examined.

The progress measure is range length. A successful pair comparison reduces it by two. Maximum active depth is approximately length / 2 + 1. The function is logically terminating for every finite valid string, yet a very large externally supplied string can still make its depth unsafe. An iterative two-index version uses constant call-stack space.

Recursive Contract Proof

A recursive correctness argument mirrors the code:

1. Base: every sequence with fewer than two elements reads the same forward and backward.
2. Local condition: for a longer sequence, its first and last elements must match.
3. Smaller problem: after matching those elements, the inner range must itself be a palindrome.
4. Progress: removing two elements makes the range strictly smaller.
5. Composition: matching ends plus a palindromic interior implies the whole range is palindromic.

This is stronger than saying “the function calls itself until it stops.” It identifies why the returned value describes the original input. A recursion can terminate and still be wrong if it combines the smaller result incorrectly or removes the wrong portion of state.

Frame Budget

Every active call stores implementation-dependent information: return location, saved execution state, parameters or their effective values, and automatic locals not optimized away. C exposes no portable function that says how many frames remain.

Estimate depth from the input and contract instead:

countdown by one             depth proportional to n
strip two endpoints          depth proportional to n/2
divide positive value by 2   depth proportional to log2(n)
mutual recursion             count progress across the full call cycle

Then impose a limit, convert to iteration, or use explicit allocated work storage when external input can exceed the safe design bound. Reducing local arrays inside a frame may postpone exhaustion but does not make unbounded depth acceptable.

Failure Propagation

If a recursive operation can fail, every caller must decide what happens to work performed before the child call. A Boolean pattern is:

if (!process_child(next_state)) {
    return false;
}
return finish_current_state();

If the current frame acquired a resource before descending, it must release that resource on both child success and failure. When several frames have acquired resources, failure unwinds through all of them in reverse acquisition order. This resembles ordinary function cleanup, multiplied by depth.

Avoid using a valid computed value as a failure sentinel when the recursion’s range includes that value. Return status separately through an output pointer, or return a structure containing status and value. The interface should let the first deep failure propagate without being mistaken for a normal base result.

Checked Range Sum

Recursive arithmetic needs both structural and numeric correctness. This complete program sums a half-open array range while refusing signed overflow.

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

static bool add_checked(long left, long right, long *result) {
    if (result == NULL) {
        return false;
    }
    if ((right > 0 && left > LONG_MAX - right) ||
        (right < 0 && left < LONG_MIN - right)) {
        return false;
    }
    *result = left + right;
    return true;
}

static bool sum_range(const int values[], size_t count, long *result) {
    if (result == NULL || (values == NULL && count != 0)) {
        return false;
    }
    if (count == 0) {
        *result = 0;
        return true;
    }

    long suffix;
    if (!sum_range(values + 1, count - 1, &suffix)) {
        return false;
    }

    long combined;
    if (!add_checked(values[0], suffix, &combined)) {
        return false;
    }
    *result = combined;
    return true;
}

int main(void) {
    int values[] = {7, -2, 11, 4};
    size_t count = sizeof values / sizeof values[0];
    long total;

    if (!sum_range(values, count, &total)) {
        fputs("sum unavailable\n", stderr);
        return EXIT_FAILURE;
    }
    printf("sum=%ld\n", total);
    return EXIT_SUCCESS;
}

The empty range has sum zero. For a nonempty range, the recursive call sums the suffix and the current frame adds the first value. Output is written only when the complete subtree succeeds, so a failure deep in recursion propagates without publishing a partial result.

For [7, -2, 11, 4], descent postpones addition:

sum([7,-2,11,4]) waits for sum([-2,11,4])
sum([-2,11,4])   waits for sum([11,4])
sum([11,4])      waits for sum([4])
sum([4])         waits for sum([])
sum([])          returns 0

Unwinding combines in reverse:

4 + 0   -> 4
11 + 4  -> 15
-2 + 15 -> 13
7 + 13  -> 20

This recursion has one frame per element plus the base frame. It is pedagogically clear but operationally inferior to a loop for a potentially large flat array. The array is linearly shaped; iteration expresses the same state with constant call-stack usage. Recursion is not more correct because it is more mathematical-looking.

Converting the Frames

To convert a linear recursion, list what every frame waits to do:

frame input: current pointer and remaining count
pending work: add current value after suffix returns
returned state: suffix sum or failure

A forward loop can instead maintain an accumulated prefix:

long total = 0;
for (size_t i = 0; i < count; i++) {
    long next;
    if (!add_checked(total, values[i], &next)) {
        return false;
    }
    total = next;
}
*result = total;

The order of checked additions differs from the recursive suffix order. For exact integer arithmetic without overflow, associativity gives the same result. With floating arithmetic, different grouping can produce different rounding. With overflow checks, one grouping may fail at an intermediate value even if another grouping stays in range. “Equivalent iteration” must include numeric semantics, not only final algebra.

Recursion Debugging

When a recursive function fails, inspect one frame as a contract instance:

input state valid?
base case correct and ordered before dangerous operations?
recursive argument strictly smaller under the progress measure?
returned failure propagated?
returned success combined with local state correctly?
resource released on both paths?

In a debugger, compare several adjacent frames. If the progress parameter repeats, the descent may cycle. If it wraps from zero to a huge unsigned value, the base check occurred too late. If inputs shrink correctly but results become wrong during unwinding, focus after the recursive call.

Logging entry and exit with depth can make structure visible:

enter n=3
  enter n=2
    enter n=1
    leave n=1 result=...
  leave n=2 result=...
leave n=3 result=...

Keep logging bounded. Printing at every frame for a huge input can change timing, consume storage, and bury the first anomalous transition.

Recursive Data Boundary

Recursion is natural when input is recursively nested: parenthesized expressions, directory-like hierarchies, or records containing child records. The code structure can mirror “process this node, then its children.” Yet external data may be adversarially deep even when total size is moderate.

A parser should enforce a maximum nesting depth before making the next recursive call. That limit is part of the accepted grammar and resource contract. Returning a clear “nesting too deep” status is preferable to relying on a process crash. An explicit work stack can move storage to checked dynamic allocation, but it still needs a memory limit and cleanup policy.

Mutual recursion needs one shared progress argument across the cycle. Checking each function in isolation can miss A(n) -> B(n) -> A(n) with no decrease. Draw the call graph and show where every cycle reduces a well-founded measure.

Branching Calls

A recursive function may make more than one child call. A naive Fibonacci definition illustrates repeated work:

unsigned long fibonacci(unsigned int n) {
    if (n < 2U) {
        return n;
    }
    return fibonacci(n - 1U) + fibonacci(n - 2U);
}

For fibonacci(5), calls for fibonacci(3), fibonacci(2), and smaller inputs occur repeatedly. The depth is only proportional to n, but the total call count grows much faster. Numeric overflow also arrives quickly. This function is useful for tracing branching frames, not as a robust general Fibonacci implementation.

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  └─ fib(2)
└─ fib(3)       repeated subtree

Logical progress on every branch proves termination, but it does not prove acceptable work. Resource reasoning needs both maximum simultaneous depth and total calls. C recursion mechanics and algorithm choice meet at this boundary; the Algorithms course develops systematic efficiency analysis.

Caching prior results or using a loop avoids repeated Fibonacci subproblems, but adds storage and invariant choices. Do not optimize a teaching recurrence without first identifying what it is meant to demonstrate.

Depth Guard

A public wrapper can enforce a documented maximum before recursion:

bool process_nested(const char *text, size_t length) {
    if (length > MAX_SAFE_DEPTH) {
        return false;
    }
    return process_nested_range(text, 0, length);
}

Input length is only a valid depth bound when each call consumes at least one byte and no branch can recurse without consumption. A nested grammar may have depth much smaller than length; tracking an explicit depth parameter can enforce the actual rule.

The constant should come from an application resource contract and testing, not a claim that every platform stack supports exactly that many frames. Keep per-frame automatic storage small and avoid recursive functions whose callers can bypass the guarded entry point.

Recursive Failures

• Missing or unreachable base cases: recursive descent never stops logically.
• No progress toward the base case: the same state repeats.
• Unsigned underflow: calling with n - 1U when n == 0U produces a huge value unless guarded first.
• Ignoring arithmetic overflow: a recursively correct shape can compute an invalid numeric result.
• Assuming tail-call optimisation: C does not guarantee it.
• Returning a pointer to a recursive frame’s local object: every such object expires when its call returns.
• Using external input as unbounded depth: resource exhaustion becomes user-controlled.
• Tracing only descent: return values and post-call effects occur during unwinding.

Recursion Reasoning

• Recursive calls create distinct invocation contexts with their own parameters and automatic locals.
• Base cases stop descent; recursive cases must make measurable progress and combine smaller results correctly.
• Calls unwind in reverse order, so code after the recursive call executes from deepest frame outward.
• Direct recursion calls the same function; indirect recursion follows a cycle of functions.
• Tail position leaves no pending work, but C does not guarantee frame reuse.
• Logical termination does not guarantee safe recursion depth or numeric range.
• Iterative conversion makes progress and accumulated state explicit and often controls resources better.

Recursion Problems

Identify the Cases

1. Distinguish a base case, recursive case, progress measure, and recursion depth.
2. Why does tail recursion not guarantee constant stack usage in C?
3. What is the difference between work performed during descent and during unwinding?

Unfold the Calls

4. Trace factorial(5) through every call and return.
5. Trace the exact output of show(4).
6. Draw the active frames when print_reverse("dog") reaches its base case.

Repair the Descent

7. Repair an unsigned countdown that recurses with n - 1U before checking zero.
8. Add overflow reporting to a recursive factorial function without performing the overflowing multiplication.
9. Diagnose mutual recursion where one branch calls the other with the same n.

Define the Recurrence

10. Write recursive and iterative functions to compute the sum of an integer array. State the empty-input result and compare resource use.
11. Write a recursive palindrome checker over a string using a half-open character range. Handle empty and one-character ranges.
12. Convert a tail-recursive greatest-common-divisor function into a loop and show matching traces.

Bound the Depth

13. For each function you build, state a progress measure and maximum depth in terms of input size.
14. Compare recursive and iterative string-length functions for clarity, stack use, failure modes, and asymptotic work without doing formal recurrence analysis.
15. Find a recursive function in an existing program and identify what state each frame must remember after its child call returns.