Where the Copy Lives

Lesson 1 left you a fact with a hole in it. C passes every argument by value, so the parameter is a copy of the argument and assigning to it leaves the caller's variable alone. Where is that copy? Chapter 1 supplied the other half of the answer without using it: variables declared inside a function live on the stack, and the stack is divided into frames, one for each call. Put the two together and you have the mechanism the whole language runs on. A call pushes a new frame, and that frame holds the parameters and locals of that one call. A return pops it, and everything the frame contained ceases to exist.

  while doubled is running            after doubled returns

  +--------------------------+        +--------------------------+
  |  doubled's frame: n      |        |  main's frame: score     |
  +--------------------------+        +--------------------------+
  |  main's frame: score     |
  +--------------------------+

Read that as a picture of order and lifetime, not of addresses. Which end of memory the frames actually sit at, and in which direction they grow, is the implementation's business, exactly as chapter 1 said about the arrangement of locals inside a frame.

Two Names, Two Addresses

The picture makes a prediction you can check with the %p printing from chapter 1: if score and n are in different frames, they are different variables, and different variables are at different addresses.

#include <stdio.h>

int doubled(int n)
{
    printf("doubled: n is %d, at %p\n", n, (void *)&n);
    return n * 2;
}

int main(void)
{
    int score = 21;

    printf("main:    score is %d, at %p\n", score, (void *)&score);
    printf("result:  %d\n", doubled(score));

    return 0;
}

main:    score is 21, at 0xfbffa15f0030
doubled: n is 21, at 0xfbffa15f0040
result:  42

Same value, two addresses. Those particular numbers came from one run and will be different on the next, for the reason chapter 1 gave, and the fact that one is higher than the other means nothing at all. What does mean something is that they differ within a single run: n is not another name for score, it is a second variable in a second frame that was handed a copy of the first one's value. Pass by value stops being a rule to memorize at that point and becomes geography. Assigning to n writes into doubled's frame, score is in main's frame, and neither can reach the other.

None of this is limited to two frames. When main calls outer and outer calls inner, three frames are alive at once, stacked in the order the calls happened, and they come off in the reverse of that order: inner returns first, then outer, then main. Last frame on is the first frame off, always, which is why the arrangement is called a stack.

A Call Is a Call, Even to Itself

A function is allowed to call itself. That sounds like a paradox until you look at the picture again, where it is nothing of the sort: a call pushes a frame with its own parameters, and the frame does not care which function issued the call. Recursion is a function written in terms of itself, and it needs two parts. Write the base case first: the input simple enough to answer outright, with no further call. Then write the recursive step, which does one piece of the work and hands a strictly smaller problem to another call of itself. Get the base case down before anything else, because it is the only thing that stops the chain.

#include <stdio.h>

void countdown(int n)
{
    if (n == 0)
    {
        printf("liftoff\n");
        return;
    }

    printf("counting %d\n", n);
    countdown(n - 1);
    printf("back at %d\n", n);
}

int main(void)
{
    countdown(3);

    return 0;
}

counting 3
counting 2
counting 1
liftoff
back at 1
back at 2
back at 3

Read the trace against the frames. main calls countdown(3), which prints and calls countdown(2), which prints and calls countdown(1): three countdown frames now sit on top of main's, each holding its own n, all three alive at the same time. countdown(0) matches the base case, prints liftoff and returns without calling anything, and the pops begin. The last three lines are the proof that each frame kept its own copy: the frame that resumes first is the one that was pushed last, and its n is still 1, undisturbed by everything the deeper calls did. That is the entire idea. A recursive call is not a jump back to the top of the function, it is an ordinary call to an ordinary function that happens to have the same name.

When the Base Case Is Never Reached

The next program is wrong. It is the countdown above with one character changed, a + where the - was, and the base case it will never reach is still sitting right there at the top of it.

#include <stdio.h>

void countdown(int n)
{
    if (n == 0)
    {
        printf("liftoff\n");
        return;
    }

    printf("counting %d\n", n);
    countdown(n + 1);
    printf("back at %d\n", n);
}

int main(void)
{
    countdown(3);

    return 0;
}

It compiles without a single warning, because nothing here is wrong as C: the compiler has no way to know which values will reach the function. Run it and the counting climbs away from the base case instead of toward it, until the program dies. This is the report, trimmed, with frames #0 to #2 left out because they are inside printf, which is merely where the last of the memory happened to run out:

counting 3
counting 4
counting 5
...
==13==ERROR: AddressSanitizer: stack-overflow on address 0xfffff39d8fe0 (pc 0xffffa186e764 bp 0xfffff39d9a20 sp 0xfffff39d8fe0 T0)
    #3 0x000000400988 in countdown /tmp/countdown.c:11
    #4 0x000000400a08 in countdown /tmp/countdown.c:12
    #5 0x000000400a08 in countdown /tmp/countdown.c:12
...
SUMMARY: AddressSanitizer: stack-overflow /tmp/countdown.c:11 in countdown

Be precise about what that is, because it is easy to mistake for a helpful language feature. The stack is a region of finite size, and every live frame costs some of it. Frames kept going on and none came off, so the program eventually reached past the end of the region. C itself has nothing to say about this: there is no error, no exception, and no depth limit written into the language. What turned it into a readable report is AddressSanitizer, which this platform compiles into every program and which notices the moment the stack is walked off its end. Build the same source without a sanitizer and the usual outcome is a bare segmentation fault with no explanation at all. Do not read the frame count in a report as a budget either, since how many calls fit depends on the frame size, the optimizer, the sanitizer and the operating system's stack limit, and it will not be the same number tomorrow.

Putting the minus sign back gives you the working countdown from the previous section, and the rule that program obeys is worth stating on its own. Every recursive step must move the argument toward the base case, by an amount that cannot skip it. Both halves matter: countdown(n + 1) fails the first half, and a version stepping n - 2 from an odd number would pass the first and fail the second, sailing straight past n == 0 into the negatives. Then keep the depth bounded and shallow, because a compiler is permitted but never obliged to reuse a frame rather than push one. C offers no tail-call guarantee. gcc often does turn a call sitting in the last position of a function into a jump, which is why a bottomless recursion sometimes spins forever instead of crashing, but that is an optimization you were lucky to receive rather than a promise you can design around.

Loop or Recursion

Anything you can write as a loop you can write as a recursion, and the other way round, so the choice is about reading rather than power. In C the loop is the everyday tool: it costs one frame no matter how many times it runs, it cannot exhaust the stack, and for counting, totalling and stepping through data it is what another C programmer expects to see. Recursion earns its place when the problem is self-similar, when solving it plainly means solving one or two smaller copies of itself, and chapter 6 is where you will first be able to build data shaped that way. Until then, reach for recursion when it makes a definition read like its own description, as sum_digits does in this lesson's exercise, and reach for a loop the rest of the time.

Key Takeaways

  • A call pushes a frame onto the stack holding that call's parameters and locals, and return pops it. The frame is the whole lifetime of a local variable.
  • Frames come off in the reverse of the order they went on. main calls outer calls inner, and inner returns first.
  • Pass by value is a consequence of the frame picture: the parameter is a different variable in a different frame, at a different address, which you can see by printing &score in the caller and &n in the callee.
  • Recursion is a function calling itself, and every call gets its own frame with its own copy of the parameters. Write the base case first, then a recursive step that moves strictly toward it.
  • A base case that is never reached exhausts the stack. That is not an error the language defines: here AddressSanitizer reports stack-overflow, without a sanitizer it is usually a bare segmentation fault. Never treat the depth reached as a number to rely on.
  • C gives no tail-call guarantee, so keep recursion shallow and bounded. Loops are the everyday tool in C; recursion is for problems that are genuinely self-similar.