Recursion for Beginners: Base Case, Progress and Returning Results

What is recursion?

Writing a function that calls itself is easy. Explaining why it stops and how its returned result contributes to the original question is the important part.

Trace a small sum

For a non-negative integer n, the sum from 1 to n can be described as n plus the sum from 1 to n - 1. At n = 0, the sum is zero. The example uses the fixed input 5 and produces 15.

#include <stdio.h>

/* Teaching example: called only with the fixed input 5. */
int sum_to(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main(void) {
    printf("%d\n", sum_to(5));
    return 0;
}

The return phase gives 1, then 3, then 6 for this smaller trace. The initial example with 5 extends the same chain to 15.

Why does it terminate?

For the fixed non-negative input, each recursive call reduces n by one until n reaches zero. The base case is checked before subtracting again, so zero does not lead to an unsigned wraparound call.

This is a small teaching example, not a function to expose to arbitrary input. Large values can exceed the result type's range or use excessive call-stack space. A general interface needs explicit limits or a different method.

Count the hidden space

Each active call has state that must be preserved until its smaller call returns. This simple linear recursion therefore uses O(n) call-stack space in the usual execution model, as well as O(n) calls.

A short function body does not imply constant memory. Do not assume the compiler will remove the recursive calls; this example also has addition to perform after the recursive result arrives.

Compare with an iterative approach

A loop can calculate the same small sum using a running total and a counter. That uses constant auxiliary state. A formula may also be possible, but arithmetic overflow and the input contract still need attention.

Recursion is not automatically better or worse. It is particularly natural when the problem itself has a recursive structure, such as visiting subtrees. Choose it because the reasoning is clear and the costs fit.

Your practice task

Draw the call and return sequence for n = 4. The answer is 10. Label where the base case occurs and which additions happen while results return.

Then explain what would go wrong if the base case were missing. Practise small, bounded examples before moving to tree traversals or more complex recursive algorithms in your learning route.