C functions, the runtime stack and recursion

Until now everything was inside main. Real programs are divided into functions: each does a single job, has a name, takes parameters, returns a value. This page explains the rules of functions in C, how they work on the LC-3 (the runtime stack) and functions that call themselves (recursion). Two kinds of questions come up on the exam: “What is printed?” and “draw the stack: where is R5, at which offset is the parameter?”.

Function definition

int square(int x) {      /* return type, name, parameter list */
    return x * x;
}

int main(void) {
    int r = square(4);   /* argument 4 */
    printf("%d\n", r);
    return 0;
}

• Parameter: the variable in the function definition (x).
• Argument: the value given in the call (4).
• Prototype: if the function will be defined after main, it is declared beforehand: int square(int x);.
• A void return type: returns no value.

Call by value

In C the value of the argument is copied. If the function changes its parameter, it changes only its own copy.

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

int main(void) {
    int x = 1, y = 2;
    swap(x, y);
    printf("%d %d\n", x, y);
    return 0;
}

1 2

The explanation at the LC-3 level is simple: the arguments are copied onto the stack, swap changes those copies, and when the function returns that region is discarded from the stack. For a swap you need to pass the addresses of x and y (pointers, week 13).

Scope and lifetime

int counter(void) { static int c = 0; c++; return c; }

The first call returns 1, the second 2, the third 3. Without static, 1 every time.

The runtime stack

For every function call, an activation record (or stack frame) is opened in memory. The records are kept in stack order: last in, first out (LIFO). When main calls a function, its record is placed on top of main’s; when the function returns, it is removed. This is why recursion works: each call has its own record, that is, its own n.

In the LC-3 C compiler:

The stack grows toward lower addresses: push = decrease R6 by one, then write.

The structure of the activation record

low address
            +--------------------+
  R5 - 1 →  | 2nd local variable |
  R5     →  | 1st local variable |
  R5 + 1    | dynamic link       |  the caller's R5
  R5 + 2    | return address     |  the caller's R7
  R5 + 3    | return value       |
  R5 + 4    | 1st argument       |  pushed by the caller
  R5 + 5    | 2nd argument       |
            +--------------------+
high address

The calling steps

The caller:

1. Push the arguments onto the stack from right to left (so the 1st argument is closest to the top).
2. JSR function.
3. On return, read the return value at the top, and discard the return value and the arguments from the stack.

The callee:

1. Make room for the return value (R6 - 1).
2. Push R7 (the return address).
3. Push R5 (the dynamic link).
4. R5 ← R6 - 1 (the new frame), make room for local variables.
5. Run the body; access locals with LDR/STR Rx, R5, #-k, arguments with LDR Rx, R5, #4+k.
6. Write the return value to R5 + 3, discard the locals, restore R5 and R7, RET.

Worked example: add2(3, 9)

int add2(int a, int b) { int s; s = a + b; return s; }
/* main: r = add2(3, 9); */

In the simulator, initially R6 = R5 = x4000. Inside add2, right after the line s = a + b, the stack is:

address content  relative to R5  meaning
x3FFA   x000C    R5 + 0      s = 12
x3FFB   x4000    R5 + 1      dynamic link (main's R5)
x3FFC   x300B    R5 + 2      return address (the instruction after JSR)
x3FFD   x0000    R5 + 3      return value (not written yet)
x3FFE   x0003    R5 + 4      a = 3
x3FFF   x0009    R5 + 5      b = 9

R5 = x3FFA, R6 = x3FFA

The LC-3 counterpart of the body:

        LDR  R0, R5, #4     ; a
        LDR  R1, R5, #5     ; b
        ADD  R0, R0, R1
        STR  R0, R5, #0     ; s = a + b

After the return, main reads R0 = 12 from the top, and R6 becomes x4000 again.

Recursion

A recursive function has two parts:

1. The base case: a small case answered without recursion.
2. The recursive step: reducing the problem and calling itself.

If there is no base case or the problem does not shrink, the stack overflows.

int fact(int n) {
    if (n <= 1) return 1;        /* base case */
    return n * fact(n - 1);      /* reduced problem */
}

fact(4)
= 4 * fact(3)
= 4 * (3 * fact(2))
= 4 * (3 * (2 * fact(1)))
= 4 * (3 * (2 * 1))
= 24

At the deepest moment there are four fact records and main’s record on the stack.

Print order: before or after?

void p(int n) {
    if (n == 0) return;
    printf("%d ", n);   /* going down */
    p(n - 1);
    printf("%d ", n);   /* coming back up */
}

p(3):

3 2 1 1 2 3

The rule: work before the recursive call is done in order on the way down, work after it is done in reverse order as the stack unwinds.

The call tree

For functions that call themselves twice, draw a tree:

                 fib(4)
              /         \
         fib(3)          fib(2)
        /      \         /     \
    fib(2)   fib(1)  fib(1)  fib(0)
    /    \
fib(1) fib(0)

number of nodes = 9 calls, fib(4) = 3

15 calls for fib(5). The same subproblems (like fib(2)) are computed again and again.

Common mistakes

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

int main(void) {
    int x = 1, y = 2;
    swap(x, y);
    printf("%d %d\n", x, y);
    return 0;
}

int f(int x) { x = x * 2; return x + 1; }

int main(void) {
    int a = 5;
    int b = f(a);
    printf("%d %d\n", a, b);
    return 0;
}

int counter(void) { static int c = 0; c++; return c; }
int plain(void) { int c = 0; c++; return c; }

int main(void) {
    counter();
    counter();
    printf("%d %d\n", counter(), plain() + plain());
    return 0;
}

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}
/* in main: */ printf("%d\n", fact(5));

void p(int n) {
    if (n == 0) return;
    printf("%d ", n);
    p(n - 1);
    printf("%d ", n);
}

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

int add2(int a, int b) { int s; s = a + b; return s; }

int dsum(int n) { if (n < 10) return n; return n % 10 + dsum(n / 10); }
int power(int b, int e) { if (e == 0) return 1; return b * power(b, e - 1); }
/* in main: */ printf("%d %d\n", dsum(4705), power(3, 4));

void rev(int n) { if (n == 0) return; printf("%d", n % 10); rev(n / 10); }
void up(int n)  { if (n == 0) return; up(n / 10); printf("%d", n % 10); }
/* in main: */ rev(123); printf(" "); up(123);