C functions and the call stack explained

Functions and the stack

A function packages some code under a name. In C you state the return type and the type of every parameter:

int square(int n) {
    return n * n;
}

So where do n and any other local variables live? In a region of memory called the stack. Each time a function is called, the program reserves a chunk of stack called a frame for that call: its parameters, its locals and the bookkeeping needed to get back to the caller. When the function returns, the frame is released and the next call reuses that memory.

Two consequences:

Locals only exist while their function is running. Once it returns, they are gone. Keeping a pointer to a local (you will meet pointers soon) and using it after the function returns is undefined behaviour, a famous C bug.
Each call gets its own frame, so two calls never share locals, even calls to the same function.

That second point is what makes recursion work: a function calling itself.

int factorial(int n) {
    if (n <= 1) return 1;          // base case: stop here
    return n * factorial(n - 1);   // a new frame with a smaller n
}

factorial(4) pushes frames for n = 4, 3, 2, 1, then the answers come back down as each frame returns: 1, 2, 6, 24. Forget the base case and the frames keep piling up until the stack runs out of room. That crash is a genuine stack overflow, the thing a certain famous Q&A website is named after.

(Strictly, the C standard never says "stack": it just says how long locals live. But every mainstream implementation uses one, including this WebAssembly one.)

Try it yourself

Edit it. Break it. Run it again.

#include <stdio.h>

int depth_demo(int n) {
    printf("entering frame with n = %d\n", n);
    if (n == 0) {
        printf("base case reached\n");
        return 0;
    }
    int result = n + depth_demo(n - 1);
    printf("leaving frame with n = %d, result %d\n", n, result);
    return result;
}

int main(void) {
    printf("sum is %d\n", depth_demo(3));
    return 0;
}

Your turn

Type it yourself. That is the whole trick.

1Your own function

Write a function int cube(int n) that returns n * n * n. Then, in main, use it in a loop to print the cubes of 1 to 4, like this:

1 cubed is 1
2 cubed is 8
3 cubed is 27
4 cubed is 64

#include <stdio.h>

int cube(int n) {
    return 0;
}

int main(void) {
    for (int i = 1; i <= 4; i++) {
        printf("%d cubed is %d\n", i, cube(i));
    }
    return 0;
}

2Recursive power

Write a recursive function int power(int base, int exp) that returns base to the power exp, using the rule: anything to the power 0 is 1, otherwise base * power(base, exp - 1). Print power(2, 10) and power(3, 4) on separate lines:

1024
81

#include <stdio.h>

int power(int base, int exp) {
    // base case first, then the recursive call
    return base;
}

int main(void) {
    printf("%d\n", power(2, 10));
    printf("%d\n", power(3, 4));
    return 0;
}