Recursion fundamentals

Overview

A recursive function solves a problem by calling itself on a smaller version of the same problem. Two ingredients are mandatory and neither is optional: a base case that returns without recursing, and a recursive step that makes measurable progress toward that base case. Miss the base case and the recursion never stops; fail to shrink the input and it never arrives. Factorial and digit-sum are the classic first examples because the shrinkage is obvious — n becomes n-1, and n becomes n/10.

Why it matters

Recursion is the natural way to express anything defined in terms of itself: trees, nested structures, grammars, filesystems, and divide-and-conquer algorithms. A directory walk or a JSON parser written iteratively needs an explicit stack; written recursively it mirrors the shape of the data. Learning to see the base case and the shrinking step is the skill that makes all of that tractable.

Core concepts

The two obligations. Base case (stop) and progress (shrink). Every recursive function you write should let you point at both.

The call stack. Each call gets its own frame holding its parameters and locals. factorial(5) builds five frames, and they unwind in reverse as each returns. That stack is finite — typically around 1 MB — so depth is a real resource, unlike in a loop.

Trust the recursion. When writing the recursive step, assume the smaller call already returns the right answer and just combine it correctly. Mentally tracing every level is how people talk themselves out of correct code.

Progress must be guaranteed. n-1 shrinks toward 0; n/10 shrinks toward a single digit. A step like n-0 or a conditional that sometimes fails to shrink causes infinite recursion for some inputs — the bug that only shows up on the input you did not test.

Recursion vs iteration. Anything recursive can be written iteratively and vice versa. Choose recursion when it matches the structure of the data; choose iteration when depth could be large or the loop is simply clearer.

Syntax notes

/* base case + a step that shrinks toward it */
long long factorial(int n) {
    if (n <= 1) return 1;                 /* base case: stops the recursion */
    return (long long)n * factorial(n - 1);   /* progress: n shrinks by 1 */
}

int sum_digits(int n) {
    if (n < 10) return n;                 /* base case: a single digit */
    return n % 10 + sum_digits(n / 10);   /* progress: one digit removed */
}

Key points:

• n <= 1 (not n == 1) so factorial(0) and negative inputs terminate.
• Cast to long long before multiplying, or the product overflows as int first.
• sum_digits assumes non-negative input; a negative n would need its own handling.

Lesson

A recursive function solves a problem by calling itself on a smaller input, stopping at a base case. Two ingredients are mandatory: a base case that returns without recursing, and a recursive step that moves toward it. Factorial and digit-sum are the classic first examples.

Code examples

#include <stdio.h>
/* A recursive function calls itself on a smaller input until a base case stops it. */
static long long factorial(int n){ if(n<=1) return 1; return (long long)n*factorial(n-1); }
static int sum_digits(int n){ if(n<10) return n; return n%10 + sum_digits(n/10); }
int main(void){
    printf("factorial(6) = %lld\n", factorial(6));
    printf("sum of digits of 2025 = %d\n", sum_digits(2025));
    return 0;
}

Line by line

Common mistakes

Missing or unreachable base case (stack overflow); a step that doesn't shrink the input.

Debugging tips

Compiler errors and warnings:

• warning: infinite recursion detected — some compilers spot the missing or unreachable base case.
• -Wreturn-type if a path through the function forgets to return a value.

Runtime symptoms:

• Segmentation fault immediately. Stack overflow from infinite recursion. Check that the base case is reachable and that the argument really shrinks.
• Works for small inputs, crashes for large ones. Genuine stack exhaustion — the depth is proportional to the input. Convert to iteration or add memoization.
• factorial(0) returns 0 or loops. The base case is n == 1 instead of n <= 1.
• Wrong results above 12 or 20. Overflow: 13! exceeds 32 bits and 21! exceeds 64. Cast before multiplying and pick the right width.

Technique: add a temporary printf of the argument at the top of the function. If the printed values do not march steadily toward the base case, you have found the bug.

Memory safety

• The call stack is a bounded resource. Each frame costs memory; roughly a million frames will exhaust a typical 1 MB stack. Unbounded recursion driven by user input is a denial-of-service vector, not merely a crash.
• No heap involved here, so nothing to free — but that also means a stack overflow gives you no graceful failure path. It is a hard crash.
• Signed overflow is undefined behaviour. factorial overflows quickly; cast to the wide type before the multiplication, not after.
• Validate the input range. Decide what factorial(-5) should do and enforce it, rather than relying on n <= 1 to catch it by accident.
• Tail calls are not guaranteed to be optimised in C. Do not assume a tail-recursive function runs in constant stack space; the standard makes no such promise, and it depends on the compiler and flags.

Real-world uses

Concrete uses: Walking a directory tree, parsing nested JSON or XML, evaluating an expression tree, traversing a linked structure, and every divide-and-conquer sort. Compilers use recursive-descent parsing. Graphics code recurses over scene graphs; filesystems recurse over directories.

Professional best practices:

Beginner:

• Write the base case first, before the recursive step.
• Say out loud how the argument shrinks; if you cannot, the function is not ready.

Intermediate:

• Bound the depth when the input is untrusted, or convert to an explicit stack.
• Prefer iteration for simple linear traversals — recursion earns its keep on branching structures.
• Choose accumulator widths deliberately; recursive numeric functions overflow fast.

Practice tasks

1. (Beginner) Factorial. Implement long long factorial(int n) with a base case covering 0 and 1. Example: factorial(5) -> 120; factorial(0) -> 1. Concepts: base case, overflow-safe casting.

2. (Beginner) Digit sum. Implement int sum_digits(int n) for non-negative n. Example: 472 -> 13. Concepts: shrinking by division.

3. (Intermediate) Count down safely. Write a recursive function that prints n down to 1, then add a depth guard that refuses inputs above 10,000. Concepts: stack limits, defensive bounds.

4. (Intermediate) Iterative twin. Rewrite both functions as loops and compare results across many inputs. Concepts: recursion/iteration equivalence.

Summary

Every recursive function needs exactly two things: a base case that returns without recursing, and a step that shrinks the input measurably toward it. Trust the smaller call to be correct and focus on combining its result properly — tracing every level by hand is unnecessary and misleading. Remember that each call consumes a stack frame, so depth is a bounded resource in a way loop iterations are not, and C does not guarantee tail-call optimisation. Guard the base case for edge inputs (n <= 1, not n == 1) and widen accumulators before arithmetic overflows.

Practice with these exercises

• Recursive factorial
• Sum of digits