Functions in C: parameters, scope, the call stack and recursion

A long program written entirely in main soon becomes unreadable. Functions let you split the problem into parts, each with a name, parameters and a result, to be written, tested and reused separately. In this lesson we see how they are defined, how parameters are passed, what happens in memory during a call (the stack) and recursion.

Definition and call

#include <stdio.h>

/* prototype: tells the compiler the name, parameters and result type */
double divider(double vin, double r1, double r2);

int main(void)
{
    double vout = divider(12.0, 10e3, 4.7e3);
    printf("Vout = %.2f V\n", vout);         /* Vout = 3.84 V */
    return 0;
}

/* output voltage of a resistive divider */
double divider(double vin, double r1, double r2)
{
    return vin * r2 / (r1 + r2);
}

• The prototype before main lets you use the function before defining it. Prototypes are usually collected in a .h header file.
• The formal parameters (vin, r1, r2) are local variables that receive the values of the arguments passed in the call.
• return ends the function and returns the value. A function that returns nothing has type void.

Pass by value

In C arguments are passed by value: the function gets a copy, and changing it does not change the caller’s variable.

void twice(int x) { x = 2 * x; }      /* changes only the local copy */

int main(void)
{
    int n = 5;
    twice(n);
    printf("%d\n", n);                /* prints 5, not 10 */
    return 0;
}

To let a function change a caller’s variable, or return more than one result, you pass its address: the subject of the lesson on pointers, and the reason scanf wants &n.

Scope and lifetime of variables

• Local variables, declared inside a function or block, exist only while that block runs and are visible only there.
• Global variables, declared outside every function, exist for the whole program and are visible everywhere. Convenient but dangerous: any function can change them, and finding who did is hard.
• A static local variable keeps its value between calls: useful for a counter internal to a function.

The call stack

Each function call creates in memory an activation record (stack frame) holding the parameters, the local variables and the return address. Records pile up on the stack: the one on top is the running function; on return it is removed and execution resumes in the caller.

That is why local variables “vanish” at the end of the function: their space is reused by the next call. Returning the address of a local variable is one of the most serious mistakes in C.

Recursion

A recursive function calls itself on a smaller problem. It needs two ingredients: a base case solved directly and a recursive step that shrinks the problem towards the base case.

unsigned long fact(unsigned int n)
{
    if (n <= 1) return 1;          /* base case */
    return n * fact(n - 1);        /* recursive step */
}

Recursion is natural for problems that contain smaller copies of themselves: tree structures, “divide and conquer” algorithms such as merge sort and the FFT, exploring a maze.

The costs. Each call takes stack space. With too deep a recursion the stack runs out (stack overflow) and the program crashes: a real risk on microcontrollers, where the stack is a few kilobytes. Some recursions also repeat a lot of work: Fibonacci written as fib(n) = fib(n-1) + fib(n-2) recomputes the same values an exponential number of times; fib(40) needs over 300 million calls. The loop version needs 40 steps.

unsigned long fib(unsigned int n)
{
    unsigned long a = 0, b = 1;
    for (unsigned int i = 0; i < n; i++) {
        unsigned long t = a + b;
        a = b;
        b = t;
    }
    return a;
}

Designing with functions

A good function does one thing, has a name that describes it, few parameters and no hidden side effects. It can be checked on its own, with a small test program that calls it with values whose result is known: the idea behind unit tests. The C standard library (<math.h>, <string.h>, <stdlib.h>) is an example of small, reusable functions: before writing one, check whether it already exists.