66. Functions, scope, recursion

A function is a piece of a program with a name, an input and an output. Everything a microcontroller program does is split into functions: main, interrupt handlers, drivers, operating system tasks.

This section is about how a function is declared and called, what really happens to the arguments, where variables live and for how long. And about recursion — an elegant technique, but on a chip with a few kilobytes of RAM it calls for a separate talk about the stack.

Terms used in the documentation

Term	Meaning
function declaration, prototype	a statement of the name and types, without a body
function definition	the function with its body
parameter, argument	the name in the header, the value passed in a call
pass by value	the function receives a copy
return value	what the function gives back
calling convention (AAPCS)	the rules for where arguments and results go
stack frame	the stack area of one call
scope	where a name is visible
storage duration, lifetime	how long a variable exists
automatic, static storage	memory on the stack, memory for the whole run
shadowing	a local name hiding an outer one
recursion, base case	a function calling itself, the condition that stops it
tail call	a call that is the last action of a function
call graph	which function calls which

66.1 Why functions

A function solves three problems:

• it names an action: uart_send(byte) reads better than eight lines of register work;
• it removes repetition: a fix in one place fixes all calls;
• it limits visibility: the function's variables do not get in the way of the rest of the program.

A function consists of a header — the result type, the name, the parameters — and a body:

int max(int a, int b)       /* заголовок */
{                           /* тело */
    if (a > b)
        return a;
    return b;
}

return returns a value and ends the function at once. If a function returns nothing, its type is void, and return in it is written without a value or not written at all.

66.2 Declaration and definition

The compiler reads a file from top to bottom. To call a function before its body is written, you declare it with a prototype:

int max(int a, int b);      /* объявление: имя, типы, и больше ничего */

int main(void)
{
    return max(3, 7);
}

int max(int a, int b)       /* определение: тело */
{
    return a > b ? a : b;
}

Prototypes of functions needed in several files are moved to a header file (section 71). And if there is a prototype but no body anywhere, the error comes not from the compiler but from the linker — "undefined symbol" (section 63.7).

int f() and int f(void) are not the same thing. In old C, empty parentheses mean "parameters not specified", and the compiler does not check calls:

The rule is simple: a function without parameters is declared with void in the parentheses. Then an argument error is found by the compiler, not by you while debugging.

66.3 How arguments are passed

In C, arguments are passed by value only. The function receives copies, and whatever it does with them, the caller's variables do not change:

void swap(int a, int b) { int t = a; a = b; b = t; }

int n = 7, m = 5;
swap(n, m);                 /* n = 7, m = 5 — поменялись только копии */

For a function to be able to change a variable, it is passed the address of the variable — then the address is copied, and through it you can reach the original:

void swap(int *pa, int *pb) { int t = *pa; *pa = *pb; *pb = t; }

swap(&n, &m);               /* n = 5, m = 7 */

How pointers work — section 67.

Where the arguments really are. The ARM calling rules (the AAPCS convention) are the same for all compilers, and they are worth knowing:

• the first four arguments are passed in registers r0, r1, r2, r3;
• the fifth and later ones go through the stack: the caller puts them there, and the called function reads them from there;
• the result is returned in r0.

These are the rules for 32-bit integers and pointers. A 64-bit value (int64_t, and without -mfloat-abi=hard also double) takes a register pair — r0:r1 or r2:r3: in f(int x, int64_t y) the number y goes into r2:r3, and r1 is skipped. A 64-bit result is returned in r0:r1. With -mfloat-abi=hard on Cortex-M4, floating-point arguments go into the FPU registers s0–s15, and a float result into s0 (section 77.3). A structure larger than four bytes is returned through memory: the caller passes its address as a hidden first argument in r0.

Here is the call five(1, 2, 3, 4, 5) as the compiler makes it:

movs    r0, #1
movs    r1, #2
movs    r2, #3
movs    r3, #4
mov.w   r12, #5
str.w   r12, [sp]           ; пятый — в стек
bl      five

The practical conclusion: functions with four parameters or fewer are cheaper to call. If there are many parameters, they are gathered into a structure and its address is passed (section 70). This also explains what you see in the debugger after a fault: r0–r3 from the stack frame hold the working values at the moment of the fault. If the fault happened at the start of a function, these are still its arguments; later on they can be anything (section 35.2).

66.4 Scope and lifetime

Every variable has two independent properties: where its name is visible and how long it lives.

Locals live on the stack: on entry to a function space is set aside for them, on exit it is released. That is why their value is not kept between calls and is not zeroed at startup (section 64.1).

static on a local variable changes its lifetime but not its visibility. Compare:

void count(void)        { int a = 5;        a++; printf("%d ", a); }  /* 6 6 6 */
void count_static(void) { static int a = 5; a++; printf("%d ", a); }  /* 6 7 8 */

Three calls of the first print 6, 6, 6: the variable is created anew every time. The second prints 6, 7, 8: the static variable is created once before the program starts, and the initial value 5 is assigned to it at that moment, not on every call.

An exercise on everything at once:

int y = 1;

int f(int *pa)
{
    static int x = 3;
    x += y;
    return x + *pa + y;
}

int main(void)
{
    int n = 10;
    y++;
    printf("%d ", f(&n));   /* 17 */
    printf("%d\n", f(&n));  /* 19 */
}

First call: y is already 2, x was 3 and becomes 5; 5 + 10 + 2 = 17. Second: x remembers 5 and becomes 7; 7 + 10 + 2 = 19.

static on a global variable or function makes the name invisible to other files. This is the main tool for keeping order in a multi-file project: everything not needed outside is declared static (section 3.6).

Shadowing. A local variable can have the same name as a global one — and then the global becomes inaccessible inside the block:

int level = 1;
int shadow(void) { int level = 2; return level; }    /* 2; глобальная осталась 1 */

C has no way to refer to the shadowed global from that block. The compiler is silent about shadowing even with -Wall -Wextra; only the -Wshadow option warns. The error is insidious because the code looks right: we write to level, but the wrong variable changes.

66.5 static as a function's memory

A static variable is a convenient way to give a function its own state without creating a global. An example from communications practice — a generator of a pseudo-random bit sequence used to test transmission lines:

unsigned prbs7(void)
{
    static unsigned a = 0x01;                       /* состояние между вызовами */
    unsigned bit = ((a >> 6) ^ (a >> 5)) & 1u;
    a = ((a << 1) | bit) & 0x7Fu;
    return a;
}

Seven bits give 128 combinations, but one of them, zero, is forbidden: the generator never leaves zero. The other 127 are walked through in a circle, and the sequence repeats after exactly 127 calls — the maximum for seven bits, 2⁷ − 1. So the initial value can be anything except zero. Nobody outside can corrupt the state: the name a is visible only inside the function.

A frequent question: how many static variables are there in recursion? One. However many times a function calls itself, its static variable exists in a single instance. A function that counts its entries in a static counter will see 5 in it after five nested calls — all levels share the same counter.

⚠️ static and interrupts. A function with static state must not be called at the same time from the main program and from an interrupt: the interrupt can catch the state half-updated. The same goes for RTOS tasks (section 30).

66.6 Recursion

A recursive function calls itself. It must have two parts: a base case and a step that brings it closer to it.

unsigned fact(unsigned n)
{
    if (n <= 1)                 /* условие остановки */
        return 1;
    return n * fact(n - 1);     /* шаг */
}

Each call waits for the result of the next one. fact(3) calls fact(2), that one calls fact(1), which returns 1; then the results climb back up: 2 · 1, then 3 · 2.

The order of actions relative to the call decides everything:

void rec(int n)     { if (n > 0) rec(n - 1); printf("%d ", n); }   /* 0 1 2 3 */
void rec_pre(int n) { printf("%d ", n); if (n > 0) rec_pre(n - 1); } /* 3 2 1 0 */

Printing after the call happens "on the way back" — from the bottom up.

Recursion is a convenient way to write down what is itself defined recursively:

int sum_digits(int n) { return n > 0 ? n % 10 + sum_digits(n / 10) : 0; }  /* 12345 → 15 */
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }               /* (14, 35) → 7 */

And a word about limits: fact(12) = 479001600 still fits in 32 bits, but fact(13) no longer does. Instead of 6227020800 you get 1932053504, without any warning.

66.7 The cost of recursion: the stack

Every function call gets a stack frame: the return address, saved registers, local variables. A recursive function has as many frames as the depth of the recursion.

How many bytes that is can be seen from the code. A function with a local array of 256 bytes begins with the instruction sub sp, #256 — exactly as much as it takes from the stack on every call. The recursive fib takes 16 bytes per call, and at a depth of 30 that is already 480 bytes.

On a PC the stack is megabytes. On a microcontroller it is usually a kilobyte or two, and an RTOS task may have only a few hundred bytes (section 26.7). A stack overflow causes no error by default: the stack silently runs over the neighbouring data (section 11.4). It can be caught in three ways. Cortex-M33 (L5, U5, H5) has the stack limit registers MSPLIM and PSPLIM: as soon as the stack pointer goes below the limit, a UsageFault occurs, and the memory below the limit stays intact. On other cores a no-access MPU region is placed below the stack (section 11а.4). Or memory is laid out so that the stack starts at the bottom edge of RAM: when it overflows, it goes past that edge, and the fault occurs on the very first write.

And here is the main point. The Keil linker can compute the maximum stack depth of the whole program from the call graph — the best way to find out how much stack is really needed (section 35.4). But it stops at recursion:

Maximum Stack Usage = 272 bytes + Unknown(Cycles, Untraceable Function Pointers)
Call chain for Maximum Stack Depth:
main => fib_rec => fib_rec (Cycle)

A cycle in the call graph means: nobody knows the depth. It depends on the data. That is why embedded coding standards usually forbid recursion, and where it is allowed, its depth is limited explicitly.

66.8 The cost of recursion: time

Fibonacci numbers are defined recursively — F(n) = F(n−1) + F(n−2) — and the direct form looks elegant:

long fib(int n) { return n <= 0 ? 0 : n == 1 ? 1 : fib(n - 1) + fib(n - 2); }

But each call spawns two, and the same values are computed again many times:

Almost three million calls instead of thirty steps. The number of calls grows as fast as the Fibonacci numbers themselves. How such things are estimated in advance — section 76; how they are measured — section 73.

66.9 When the compiler removes recursion by itself

If the recursive call is the last action of a function, as in gcd, the compiler with optimisation turns it into an ordinary jump: the recursion becomes a loop, and the stack does not grow.

A modern compiler goes further. With optimisation the recursive fact turns into the same loop as a hand-written iterative version — they differ by one instruction, in the order of operands. But of the two recursive calls in fib, only one can be removed.

You cannot rely on this, for two reasons. Without optimisation — and debug builds are usually built exactly that way — recursion stays recursion. And a program that works in the release build and crashes from a stack overflow in the debug build is the worst kind of bug. If the depth can be large, write the loop yourself.

66.10 Pitfalls

A function "does not change" a variable. The argument was passed by value: you need to pass the address.

An extra argument in a call went unnoticed. The declaration int f() without void.

There is a prototype, but the linker says "undefined symbol". The function body is not in any file of the project.

A counter in a function starts over every time. The variable is not static.

A static variable "does not reset". That is by design: the initial value is assigned once.

You changed a global, but the value is the same. Inside the block it is shadowed by a local with the same name. The -Wshadow option finds such places.

A function with static state sometimes returns garbage. It is called at the same time from an interrupt and from the main program.

Recursion works on a PC and crashes on the chip. The stack is thousands of times smaller.

The stack overflowed, but there is no fault. M3 and M4 have no stack limit: an MPU guard below the stack or the stack at the bottom edge of RAM; on M33 — MSPLIM.

The release build works, the debug build crashes. In the release build the optimiser removed the recursion; in the debug build it stayed.

The linker cannot compute the stack. There is a cycle in the call graph — that is recursion.

Factorial of 13 gave a strange number. A 32-bit overflow.

fib(40) takes a minute. The double recursion recomputes the same things.

66.11 Summary

• A function is declared with a prototype and defined with a body; without parameters — with void in the parentheses, otherwise the compiler will not check calls.
• Arguments are passed by value only; to change a variable, pass its address.
• On Cortex-M the first four arguments go in r0–r3, the rest through the stack, the result in r0; 64-bit values in register pairs, float with -mfloat-abi=hard in s0–s15.
• A local variable lives while its block runs; static makes it permanent but leaves it visible only in the block. The initial value of a static is assigned once.
• static at file level hides a name from other files.
• A local variable can shadow a global one; only -Wshadow warns.
• Recursion must have a base case and a step; a static variable in recursion is one for all levels.
• Every call takes a stack frame; the linker computes the stack depth of the whole program, but at recursion it reports "unknown".
• Double recursion fib(30) — 2692537 calls versus 30 loop steps.
• The optimiser turns tail and simple recursion into a loop, but in the debug build it stays.

Next: section 67 "Pointers and pointer arithmetic".