Recursion and the call stack

Why it exists

Many problems contain a smaller copy of themselves. The factorial of 4 is 4 times the factorial of 3. A folder contains folders. A tree is a root with smaller trees hanging off it. Recursion lets a function say "solve a smaller version of me, then finish the job".

There is nothing magical about it for the machine. A recursive call is an ordinary function call whose target happens to be the same function. The only new question is bookkeeping: if fact(4) is waiting for fact(3), and that is waiting for fact(2), where does the machine remember what each of them was in the middle of doing?

The answer is the call stack. Every active call owns one block of memory, a stack frame, holding its own copy of the arguments and local variables and the address to return to. Recursion works because each call gets its own frame.

Prerequisites

You should already be comfortable with: a C function receives copies of its arguments, local variables live only while the function runs, and the stack is one region of the process memory next to the code, data and heap.

Precise definitions

• Recursive function. A function that calls itself. Direct recursion: f calls f. Indirect (mutual) recursion: f calls g, and g calls f.
• Base case. An input for which the function returns without making a recursive call. Without one, the recursion never stops.
• Recursive case. An input for which the function calls itself on a smaller input, meaning one closer to a base case (not always numerically smaller). Every chain of recursive cases must reach a base case.
• Stack frame (activation record). The block of memory belonging to one call. In the simple textbook model it holds the parameters, the local (automatic) variables and the return address. Real compilers also save the caller's frame pointer and some registers.
• Active call. A call that has started and not yet returned. Frames exist only for active calls.
• Recursion depth. The largest number of simultaneously active calls. This page counts it in frames, so fact(4) reaches depth 4. Stack space is about $\text{depth} \times \text{frame size}$ when every frame has the same size.
• Winding and unwinding. The calls go down (each pushes a frame), then the returns come back up (each pops its frame). The last call made is the first to finish.

Rules that GATE questions rely on:

1. Parameters and automatic locals are per call. Two active calls of the same function have two independent copies.
2. static locals and globals exist once. All frames share them.
3. Arguments are passed by value. Changing n inside a call never changes the caller's n. (If a pointer is passed, the pointed-to object is shared.)
4. If the base case is never reached, frames keep piling up until the stack is exhausted. The C standard does not define what then happens. On typical systems the program crashes with a stack overflow, although an optimising compiler that turns a tail call into a jump may instead make the program loop forever.

How it works

Watch fact(4). Step forward with the arrow keys or the buttons. Notice the three things that change together: the stack on the left grows, the recursion tree in the middle fills in, and the highlighted line of the C source shows what the top frame is doing.

Read the animation as two phases:

1. Winding (calls). fact(4) is not a base case, so it calls fact(3) and waits. Its frame stays on the stack with 4 * fact(3) = ? pending. The same happens for fact(3) and fact(2). Four frames are alive at the deepest point.
2. Unwinding (returns). fact(1) hits the base case and returns 1. Its frame is popped. fact(2) resumes, computes $2 \times 1$, and returns 2, and so on up to 24.

The number printed under "Frame gap, real x86-64" is a real measurement. In this trace consecutive frames are 48 bytes apart. That figure comes from the instrumented build used to record the trace (the instrumentation adds a local variable and a call to printf), so an un-instrumented program can differ. The GATE model never asks you to guess it: a question that needs a frame size will state it.

Now a function with two recursive calls. fib(4) shows why the tree and the stack are different things. The tree records every call that ever happened. The stack holds only the calls that are active right now, which is always one path from the root down to the current call.

Two facts to take from this animation:

• The stack never holds more than 4 frames, the length of the longest root-to-leaf path.
• The tree has 9 nodes. The total work is the whole tree, but the total space is only one path.

Worked examples

#include <stdio.h>
 
int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}
 
int main(void) {
    printf("%d\n", fact(4));
    return 0;
}

24

#include <stdio.h>
 
void f(int n) {
    if (n == 0) return;
    printf("%d ", n);
    f(n - 1);
    printf("%d ", n);
}
 
int main(void) {
    f(3);
    printf("\n");
    return 0;
}

3 2 1 1 2 3

#include <stdio.h>
 
int calls, depth, maxdepth;
 
int fib(int n) {
    calls++;
    depth++;
    if (depth > maxdepth) maxdepth = depth;
    int r = (n < 2) ? n : fib(n - 1) + fib(n - 2);
    depth--;
    return r;
}
 
int main(void) {
    for (int n = 4; n <= 6; n++) {
        calls = depth = maxdepth = 0;
        fib(n);
        printf("%d %d\n", calls, maxdepth);
    }
    return 0;
}

9 4
15 5
25 6

#include <stdio.h>
 
int f(int x) {
    if (x <= 0) return 0;
    return f(x / 2) + 1;
}
 
int main(void) {
    printf("%d\n", f(100));
    return 0;
}

7

#include <stdio.h>
 
int g(int n) {
    static int calls = 0;
    calls++;
    if (n == 0) return calls;
    return g(n - 1);
}
 
int main(void) {
    printf("%d ", g(3));
    printf("%d\n", g(3));
    return 0;
}

4 8

Cheat box

Traps and GATE patterns

Other things examiners twist:

• Missing return on the recursive branch. Using the result of a non-void function that fell off the end without returning is undefined behaviour.
• Pass by value: modifying the parameter inside a call does not change the caller's variable. With a pointer parameter the pointer itself is still a copy, but the callee can change the pointed-to object, which is shared.
• Mutual recursion: two functions alternate frames on the stack. Draw the frames in order.

Connections

Where to look next: the frame layout here is the idea behind activation records in the compiler, the stack segment is part of the process address space, and the cost formulas are recurrence relations. When naive recursion recomputes the same subproblem again and again, memoization trades extra space for far less time.

PYQs

Consider the following C function.

void convert (int n)
{
    if (n < 0)
    printf ("%d", n);
    else {

convert (n/2);

printf ("%d", n%2);
            }
}

Which one of the following will happen when the
function convert is called with any positive integer n
as argument?

Consider the recursive functions represented by the
following code segment:

int bar(int n)

{

if (n == 1)  return 0;

else

return 1 + bar(n/2);

}

int foo(int n) {

if (n == 1)

return 1;

else   return 1 + foo(bar(n));

}

The smallest positive integer n for which foo(n)
returns 5 is ______. (answer in integer)
Note: Assume that the program compiles and runs
successfully.

Consider the following C program:
int main()
{
    f1();
    f2(2);
    f3();
    return(0);
}
int f1()
{
    return(1);
}

int f2(int x)
{
    f3();
    if (x == 1)
        return f1();
    else
        return (x * f2(x - 1));
}
int f3()
{
    return(5);
}

Which of the following options represent the
activation function corresponding to the main
function?

Consider the following C program:
#include <stdio.h>
int counter = 0;
int calc (int a, int b) {
     int c;
     counter++;
     if (b= =3) return (a*a*a) ;
      else  {
                    c = calc (a, b/3) ;
                   return (c*c*c) ;
}
}
int main ()  {
        calc (4, 81);
        printf ("%d", counter) ;
}
The output of this program is ______.

Consider the following two functions.
void fun1(int n) {
    if(n = = 0) return;
    printf("%d", n);
    fun2(n - 2);
    printf("%d", n);
}
void fun2(int n) {
    if(n = = 0) return;
    printf("%d", n);
    fun1(++n);
    printf("%d", n);
}

The output printed when fun1(5) is called is

Consider the C functions foo and bar given below:

int foo(int val) {
    int x = 0;
    while (val > 0) {
        x = x + foo(val--);
    }
    return val;
}

int bar(int val) {
    int x = 0;
    while (val > 0) {
        x = x + bar(val - 1);
    }
    return val;
}
Invocation of foo(3) and bar(3) will result in:

Consider the C function given below.
int f(int j)
{
  static int i = 50;

 int k;

 if (i == j)
  {
    printf("something");
    k = f(i);
    return 0;

  }
  else return 0;
}
Which one of the following is TRUE?

Which of the following statements are CORRECT?
1. Static allocation of all data areas by a compiler
makes it impossible to implement recursion.
2. Automatic garbage collection is essential to
implement recursion.
3. Dynamic allocation of activation records is
essential to implement recursion.
4. Both heap and stack are essential to implement
recursion.

Consider the following C-program:

void foo(int n, int sum)

{

int k = 0, j = 0;

if (n == 0)  return;

k = n % 10;

j = n / 10;

sum = sum + k;

foo(j, sum);

printf("%d,", k);

}

int main()

{

int a = 2048, sum = 0;

foo(a, sum);

printf("%d\n", sum);

getchar();
}

What does the above program print?

Self-check

#include <stdio.h>
 
void g(int n) {
    if (n > 0) {
        g(n - 1);
        printf("%d ", n);
        g(n - 1);
    }
}
 
int main(void) {
    g(3);
    printf("\n");
    return 0;
}

1 2 1 3 1 2 1

#include <stdio.h>
 
int depth, maxdepth;
 
int f(int x) {
    depth++;
    if (depth > maxdepth) maxdepth = depth;
    int r = (x <= 0) ? 0 : f(x / 2) + 1;
    depth--;
    return r;
}
 
int main(void) {
    f(100);
    printf("%d\n", maxdepth);
    return 0;
}

8

Revision card

References