The call stack and recursion

Why this matters

When one function calls another, the computer must remember where to come back to, and it must keep each call's variables separate. The structure that does this is the call stack. Understanding it explains three things you will see again and again: why local variables never clash between calls, why a function that calls itself can crash the program, and why recursion is both powerful and easy to get wrong.

Recursion is a favourite interview topic. Trees, divide and conquer, backtracking and many dynamic programming solutions are written as functions that call themselves. You will meet all of these later in the course. This lesson gives you the foundation: the call stack, the two parts every recursive function needs, and a method for checking that a recursive function will finish.

The idea: a stack of plates

Start from first principles. A program is a series of calls, and each call may start another call before it finishes. Main calls addOne, which calls triple. When triple finishes, addOne must continue from the line after its call. When addOne finishes, main must continue. Something has to hold the list of unfinished calls, in order, so that the most recent one is finished first.

A stack solves that. Think of a stack of plates in a canteen. You can only add a plate on the top, and you can only take one off the top. The last plate placed is the first one removed. This rule is called last in, first out, and programmers abbreviate it as LIFO.

The computer keeps the call stack this way. Each time a function is called, a block of memory for that call is pushed on top. When the call returns, its block is popped off. The block is called a stack frame, and it holds the call's parameters, its local variables and the return address, which is the place to come back to.

Stack frames for main, addOne and triple, with triple on top

Because each call has its own frame, two calls to the same function never share a local variable. Each frame has its own copy of n, and that is why the value n in one call does not affect the n in another.

Watching the stack grow and shrink

The next program has three functions, and each one prints a line when it starts. The printed lines show the order in which the calls begin and end.

Press Run. No input is needed. The output is:

in main
in addOne
in triple
13
back in main

Trace the stack, one event at a time.

Two details matter. First, triple(y) + 1 must wait for triple to return before it can add 1. The call is not finished until triple has sent back its result, so addOne is paused in the middle of its return statement. Second, main prints 13 only after addOne has returned, because the call to addOne is part of the expression that cout prints.

Now picture the stack when triple is running. It holds three frames. The top frame is triple, with its parameter x set to 4. Below it is addOne, with y set to 4. At the bottom is main. Each frame keeps its own variables, and the top frame is the only one that is running.

The stack in motion

The next visualiser runs a recursive function and shows its frames as they are pushed and popped. Step through it below. The function is factorial, and the input is n. Type a small number, then use the controls to move one step at a time. Watch which frame is on top, and watch the moment the answers start coming back.

Look for two things. The first is the moment the stack is deepest, when the most frames are present. The second is the moment a frame is marked as returning a value. The frame on top is the one that runs. Frames below it are waiting for their answer.

Now a second view, the same stack in a simpler form, with push and pop. Each push is a call, and each pop is a return. The list is only a demonstration of the rule, not the real call stack, but the order of events is the same.

Recursion: a function that calls itself

A recursive function is one that calls itself. It solves a problem by solving a smaller version of the same problem. Each call hands a smaller task to the next call, until the task is so small that the answer is obvious.

Think of looking up a word in a dictionary, where the definition of that word uses a second word you do not know. You look up the second word. Its definition uses a third word. You keep going until you reach a word you understand. Then you work back up, and each definition now makes sense, because each step depended on the one below.

A recursive function has exactly two parts, and every correct one has both.

1. A base case: an input so simple that the answer is written directly, with no further call. The base case stops the recursion.
2. A recursive case: a call to itself with a smaller input, so that the calls get closer to the base case.

If you forget the base case, the calls never stop. If the recursive call does not make the input smaller, the calls never reach the base case. Either mistake is a bug, and the program will crash.

Factorial: the classic example

The factorial of a number n, written n!, is the product of all whole numbers from 1 to n. So 5! is 5 × 4 × 3 × 2 × 1, which is 120. A recursive definition writes the same idea in terms of a smaller factorial: n! is n times (n − 1)!, and 1! is 1.

Press Run. No input is needed. The output is:

120

The base case is n <= 1, which returns 1. The recursive case is n * factorial(n - 1), which calls itself with a smaller number. Each call reduces n by one, so the calls reach the base case after n steps.

The return type is long long, which is a larger integer type than int. Factorials grow fast. The factorial of 13 is larger than the biggest int on most systems, so an int would overflow. You will see that mistake in the common mistakes section.

Trace the call factorial(5) in full.

1. factorial(5) starts. 5 <= 1 is false, so it computes 5 * factorial(4). It must wait for factorial(4).
2. factorial(4) starts. 4 <= 1 is false, so it waits for factorial(3).
3. factorial(3) waits for factorial(2).
4. factorial(2) waits for factorial(1).
5. factorial(1) starts. 1 <= 1 is true, so it returns 1 at once. This is the base case.
6. factorial(2) receives 1 and returns 2 × 1, which is 2.
7. factorial(3) receives 2 and returns 3 × 2, which is 6.
8. factorial(4) receives 6 and returns 4 × 6, which is 24.
9. factorial(5) receives 24 and returns 5 × 24, which is 120.

The calls go down in steps 1 to 5, and the answers come back up in steps 6 to 9. The diagram below shows the same thing as a picture: each frame waits on the one below it, and the answers flow back up.

Five factorial frames stacked: each waits for the next smaller call, and the values return upward to 120

Here is the same trace written as a tree of unfinished calls. Read it from the top down to see the calls, and from the bottom up to see the answers.

factorial(5) = 5 * factorial(4)
  factorial(4) = 4 * factorial(3)
    factorial(3) = 3 * factorial(2)
      factorial(2) = 2 * factorial(1)
        factorial(1) = 1          <- base case
      factorial(2) = 2 * 1 = 2
    factorial(3) = 3 * 2 = 6
  factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120

At the deepest point there are five frames on the stack at once. For factorial(n), the depth is n frames. Each frame holds a few bytes for its parameter and return address, so the space used by the calls is O(n). The time is also O(n), because the function makes n calls and each call does a constant amount of work.

Sum of digits: another shape

The next example splits a number into its last digit and the rest. The last digit is n % 10. The rest is n / 10, which drops the last digit. So the digit sum of 4729 is 9 plus the digit sum of 472.

Press Run. No input is needed. The output is:

22

The base case is n == 0, which means there are no digits left. The recursive case adds the last digit to the digit sum of the rest. The input gets smaller each time, because integer division by 10 removes one digit.

Trace digitSum(4729).

1. 4729 % 10 is 9, and 4729 / 10 is 472. The function returns 9 + digitSum(472).
2. 472 % 10 is 2, and 472 / 10 is 47. The function returns 2 + digitSum(47).
3. 47 % 10 is 7, and 47 / 10 is 4. The function returns 7 + digitSum(4).
4. 4 % 10 is 4, and 4 / 10 is 0. The function returns 4 + digitSum(0).
5. digitSum(0) is the base case, and it returns 0.
6. The answers come back: 4 + 0 is 4, then 7 + 4 is 11, then 2 + 11 is 13, then 9 + 13 is 22.

The function makes one call per digit. A number with d digits takes d calls, so the time is O(d), which is O(log n) in the value of the number, because each division by 10 removes one digit. The space is also O(d) for the frames.

Power: a recursion that splits the work

A power function base^exp can be written with a loop, or recursively. The recursive version uses the rule that base to the power exp is base times base to the power of exp minus one. The base case is an exponent of zero, because anything to the power of zero is 1.

To run the next program, type 2 10 in the Input box, then press Run.

Input: 2 10

Expected output:

2^10 = 1024
1+2+...+10 = 55

Trace power(2, 10) in brief. It returns 2 × power(2, 9), which returns 2 × 2 × power(2, 8), and so on. After ten multiplications the exponent reaches 0, the base case returns 1, and the ten 2s are multiplied back in, giving 1024.

Trace sumTo(10). It returns 10 + sumTo(9), and so on down to sumTo(0), which returns 0. The values add back up to 55, which is 1 + 2 + ... + 10.

Both functions make n calls for an input of n, so both are O(n) in time and O(n) in stack space. A loop would do the same work with O(1) extra space. You may ask why recursion is worth it. For these two functions, it is not. The loop is simpler. Recursion earns its place when the problem splits into parts that have the same shape, such as trees, which the next modules cover.

Counting the calls: a recursive function with two outputs

Some recursive functions do more work than a single chain. The Fibonacci sequence is the classic case. Each number is the sum of the two before it, with the first two both defined as the value of their index: fib(0) is 0 and fib(1) is 1. A direct recursive version calls itself twice, once for each of the two earlier numbers.

This version also counts how many calls it makes. The count is passed by reference, so every call adds to the same number. This ties the lesson together: recursion, a base case, and a reference from the previous lesson.

To run it, type 10 in the Input box, then press Run.

Input: 10

Expected output:

fib(10) = 55
calls: 177

The base case is n < 2. The recursive case calls fib(n - 1) and then fib(n - 2), and adds the two answers. The two calls are the reason the number of calls explodes.

Here is a short piece of the call tree for fib(4), to show the repetition. The call fib(2) appears twice, and fib(1) appears three times.

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

Every repeated call does the same work again. For n = 10 there are 177 calls, and for n = 30 there are about 2.7 million. The number of calls roughly doubles each time n goes up by one. That makes this version O(2^n) in time, which is very slow for large n. The space is still O(n), because the deepest path of frames has n levels, and at any moment only one path is on the stack.

Interviewers often ask how to fix this. The answer is to remember each result, so each smaller Fibonacci number is computed once. That is memoization, and dynamic programming, which you meet later in the course. For now, the lesson to remember is that a recursive function that calls itself twice can cost far more than the number of calls that look obvious.

Recursion versus a loop

A loop and a recursive function can often solve the same problem. The choice is about clarity and cost.

For a simple repeated step, a loop is usually better. It uses O(1) extra space, while a recursive version uses O(n) stack frames. Factorial and power are good examples: the loop version is shorter and safer.

For a problem that splits into smaller problems of the same kind, recursion is clearer. Tree traversal, divide and conquer sorting, and backtracking all have that shape. In those cases, the recursive version matches the structure of the problem, and the loop version would need a stack of its own to keep track of the work.

A useful test: does the problem split into parts that look like the whole? If yes, recursion may be the right tool. If no, a loop is probably simpler.

Designing a recursive function

Writing a recursive function is easier when you answer three questions in order.

1. What is the smallest input, and what is its answer? Write that answer as the base case. Take a function product(a, b) that multiplies a by b using only addition. The smallest b is 0, and a times 0 is 0.
2. How does a bigger problem depend on a smaller one? Write the recursive case as a formula. a times b equals a plus a times b - 1. For example, 3 times 4 is 3 plus 3 times 3.
3. Does every call move toward the base case? Check the argument in the recursive call. In product, b - 1 gets closer to 0 each time.

Once the three answers are written, you can trust the function to work for the smaller input. Programmers call this the leap of faith. You do not trace the whole chain of calls every time. You check the base case, then check that the recursive step gives the right answer when the smaller call is right. The factorial and digit-sum functions in this lesson were built this way.

int product(int a, int b) {
    if (b == 0) {
        return 0;
    }
    return a + product(a, b - 1);
}

Trace product(3, 4). The base case is not reached yet, so the answer is 3 + product(3, 3). That needs 3 + product(3, 2), then 3 + product(3, 1), then 3 + product(3, 0). The last call is the base case and returns 0. The values add back up: 3 + 0 is 3, 3 + 3 is 6, 3 + 6 is 9, and 3 + 9 is 12. The function is correct for b of 0 or more. Negative b never reaches the base case, so it needs its own check.

Stack overflow

Every frame takes space on the stack, and the stack has a fixed size. On a typical desktop system it is a few megabytes. If the recursion goes too deep, the stack runs out of space, and the program crashes. This crash is called a stack overflow.

The usual cause is a missing base case or a recursive call that does not get closer to the base case. Here is a broken function:

int down(int n) {
    return 1 + down(n + 1);   // n goes up, so the base case is never reached
}

It keeps calling itself with a bigger number, and it never returns. The frames pile up until the stack is full. When this program is run with a normal compiler setting, the operating system stops it with a segmentation fault. The shell reports the exit code 139, which is 128 plus the signal number 11. You do not need to memorise the number. Remember the crash, and the rule that prevents it.

Before you write a recursive function, ask two questions. What is the base case? Does every call make the input smaller, so that it reaches the base case in a finite number of steps? If you can answer both, the function will end.

A second cause of stack trouble is a very deep but correct recursion. A factorial of one million would need a million frames, which can overflow the stack even though the logic is right. The fix is a loop, or a different algorithm.

Recursion depth on a real system

Each recursive call uses one frame, and the stack has a fixed limit. On many Linux systems the default stack for the main thread is 8 megabytes, but the limit depends on the system and its settings. How many frames fit depends on how large each frame is, and that depends on the parameters and locals of the function. So you cannot give one exact depth that works everywhere.

As a rough guide, a recursion a few thousand levels deep is usually safe, and a recursion of a million levels usually is not. Test the real limit before you rely on it. When the depth can grow with the size of the input, prefer a loop, or choose an algorithm whose depth stays small. A binary search over a million items, for example, needs only about 20 levels, so recursion is safe there. A linear walk over a million items does not have that property.

Mutual recursion

Two functions can call each other. This is mutual recursion. Each function needs a base case, and each call must move toward one. The function isOdd must be declared above isEven, or you need a prototype for it, because isEven calls it first.

bool isOdd(int n);
 
bool isEven(int n) {
    if (n == 0) {
        return true;
    }
    return isOdd(n - 1);
}
 
bool isOdd(int n) {
    if (n == 0) {
        return false;
    }
    return isEven(n - 1);
}

Trace isEven(3). It asks isOdd(2), which asks isEven(1), which asks isOdd(0). That is the base case, and it returns false. So isEven(3) is false, which is correct. The two functions share the work, and the input shrinks by one at each call.

Worked example: a countdown

The last example shows the order of output in a recursive function. The function prints the number, then calls itself with a smaller number, and stops at zero. Because the print happens before the recursive call, the numbers come out in descending order.

Press Run. No input is needed. The output is:

3
2
1
liftoff

Trace countdown(3).

1. 3 == 0 is false. The function prints 3, then calls countdown(2).
2. 2 == 0 is false. It prints 2, then calls countdown(1).
3. 1 == 0 is false. It prints 1, then calls countdown(0).
4. 0 == 0 is true. It prints liftoff and returns. Nothing is left to do in any frame, so each frame returns in turn.

Now move the cout line below the recursive call. The output changes to liftoff, then 1, 2 and 3. The order of the lines comes from where the work happens, before the call or after it. This is a common interview question, and the answer is always to trace the frames in order.

What happens inside: the cost of one call

A call is not free. The computer must save the return address, set up a new frame, copy the arguments, run the body, and then tear down the frame. For a small function, the cost is a few machine instructions. For a recursive function that makes millions of calls, the cost adds up, and the frames take memory. Compilers can sometimes turn a recursive function into a loop when the recursive call is the last thing the function does. This is called tail call optimisation, and it depends on the compiler and the settings, so do not rely on it for correctness.

Complexity summary

Here is a summary of the recursive functions in this lesson. Use it when an interviewer asks for the cost of a recursive solution.

The rule for finding the cost is to count the calls, multiply by the cost of each call's own work, and check the deepest chain of calls for the stack space.

Common mistakes

• Missing the base case. The program runs until the stack overflows and crashes with a segmentation fault. Write the base case first.
• A recursive call that does not shrink the input. Calling f(n) from f(n) or f(n + 1) never ends. Check that each call moves toward the base case.
• Forgetting to return the recursive result. Writing factorial(n - 1); on its own, without return n *, throws the answer away. The compiler may warn about a missing return.
• Using int for a result that outgrows it. The factorial of 13 is larger than the biggest 32-bit int, so int overflows and gives a wrong answer without an error. Use long long for results that grow fast.
• Using recursion where a loop is clearer. Simple counting is easier as a loop, and it uses far less stack.
• Expecting a recursive call to finish before the next line runs in the same frame. The call finishes first, and then the line runs. Read the code as a series of calls and returns.

Debugging walkthrough: a recursive function crashes

A recursive function crashes, or returns a wrong value for some input. Work through these steps.

1. Test the base case by hand. Call the function with the smallest input, such as 0 or 1. Check that it returns the value you wrote. If it does not, the base case is wrong.
2. Test one step up. Call with 2 or 3, and trace by hand. Write the call tree on paper, as in the factorial example. Check that each level combines the results correctly.
3. Check the shrinking. Print the argument at the top of the function, using a temporary cout. If the numbers do not get smaller, the recursive call is wrong.
4. Check for a missing return. Make sure every path returns the recursive result, and that the result is combined with the right operator.

A real case: a student writes int sumTo(int n) { if (n == 0) return 0; return sumTo(n); }. Step 3 shows the argument never changes. The call passes n again, not n - 1, so the recursion never ends and the stack overflows. The fix is sumTo(n - 1).

Variations and edge cases

• Base case with more than one value. The Fibonacci function has a base case for both 0 and 1, because the recursive case needs two earlier values. Some problems need two or three base cases.
• Negative input. A function that expects a non-negative number should check its input. Factorial of a negative number has no meaning, and the base case n <= 1 returns 1, which is wrong for those inputs. Decide what the function should do, and write it down.
• A recursive function with a reference counter. As in the Fibonacci example, a reference parameter lets every call add to one total, without a global.
• Printing before or after the call. The order of the output depends on where the call sits, as the countdown showed.
• Indirect recursion. Two functions can call each other, such as isEven calling isOdd and back. The same rules apply: each path needs a base case that ends the chain.

Real-world uses

• Folders and files. Listing all files in a folder and its subfolders is a recursive walk. Each subfolder is a smaller problem of the same kind.
• Expression evaluation. A calculator that reads (2 + 3) * 4 evaluates each bracketed part first, using the same method on each part.
• Undo and search. Many search and undo features, such as a maze solver, try one choice, then recurse on the rest, and step back when the choice fails. That is backtracking.
• Parsing. Compilers and data-format readers process nested structures such as JSON with recursive functions, because the structure is nested in the same way.

Interview questions on this topic

What is the call stack? The list of unfinished function calls, stored as frames. The most recent call is on top, and each call returns to the frame below it.

What does a base case do? It gives an answer without another call, which ends the recursion. Without one, the calls never stop.

What is the time and space cost of recursive factorial? O(n) time, because there are n calls, and O(n) space, because the calls stack up n frames deep.

Why is naive Fibonacci slow? Each call makes two more calls, and many of the calls repeat work already done. The number of calls grows roughly as 2^n. Storing results of earlier calls removes the repetition.

Why might a recursive solution crash? The recursion may have no base case, may not shrink its input, or may go deeper than the stack can hold.

Practice

1. Write a recursive power(int base, int exp). The base case is exp == 0, which returns 1. Test it with power(3, 4). The answer is 81.

#include <iostream>
using namespace std;
 
int power(int base, int exp) {
    if (exp == 0) {
        return 1;
    }
    return base * power(base, exp - 1);
}
 
int main() {
    cout << power(3, 4) << endl;
    return 0;
}

2. Write a recursive sumTo(n) that returns 1 + 2 + ... + n. Test it with 10, and predict the answer first. It is 55.

#include <iostream>
using namespace std;
 
int sumTo(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sumTo(n - 1);
}
 
int main() {
    cout << sumTo(10) << endl;
    return 0;
}

3. Draw the call stack for factorial(3). Show each frame as it is pushed and popped, and write the value returned by each call.

4. Write a recursive int countDigits(int n) that returns how many digits a positive integer has. Test it with 7, 1024 and 100. The answers are 1, 4 and 3.

#include <iostream>
using namespace std;
 
int countDigits(int n) {
    if (n < 10) {
        return 1;
    }
    return 1 + countDigits(n / 10);
}
 
int main() {
    cout << countDigits(7) << endl;
    cout << countDigits(1024) << endl;
    cout << countDigits(100) << endl;
    return 0;
}

5. Write a recursive function int reverseDigits(int n) that does not need a loop. Hint: use n % 10 to get the last digit, and a helper that carries the answer so far. Test it with 4729 and expect 9274. You may use a second parameter with a default of 0.

#include <iostream>
using namespace std;
 
int reverseDigits(int n, int reversed = 0) {
    if (n == 0) {
        return reversed;
    }
    return reverseDigits(n / 10, reversed * 10 + n % 10);
}
 
int main() {
    cout << reverseDigits(4729) << endl;
    return 0;
}

6. A student writes int bad(int n) { if (n == 0) return 0; return n + bad(n); } and reports a crash. Explain why, and fix it.

7. Write a recursive function void printBinary(int n) that prints the binary digits of a non-negative number, for example printBinary(10) prints 1010. Hint: print the digits of n / 2 first, then print n % 2. Handle 0 as the base case.

#include <iostream>
using namespace std;
 
void printBinary(int n) {
    if (n < 2) {
        cout << n;
        return;
    }
    printBinary(n / 2);
    cout << n % 2;
}
 
int main() {
    printBinary(10);
    cout << endl;
    return 0;
}

8. Predict the output of void f(int n) { if (n == 0) return; cout << n; f(n - 1); } when called as f(3). Then predict what changes if the cout line moves below f(n - 1);.

9. Write a recursive function int countA(const string &s, int i) that counts the letter a in s starting at index i. The base case is i == s.size(). Test it with "banana" and index 0. The answer is 3. Include the needed headers.

#include <iostream>
#include <string>
using namespace std;
 
int countA(const string &s, int i) {
    if (i == (int)s.size()) {
        return 0;
    }
    int here = 0;
    if (s[i] == 'a') {
        here = 1;
    }
    return here + countA(s, i + 1);
}
 
int main() {
    cout << countA("banana", 0) << endl;
    return 0;
}

10. Explain why fib(40) in the naive version would take far longer than fib(30). Give a rough factor.

11. Write a recursive int gcd(int a, int b) using the rule gcd(a, b) = gcd(b, a % b), with the base case b == 0, which returns a. Test it with gcd(84, 36). The answer is 12.

#include <iostream>
using namespace std;
 
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
 
int main() {
    cout << gcd(84, 36) << endl;
    return 0;
}

What you now know

• The call stack holds one frame per unfinished call, in last in, first out order. A frame holds the parameters, the locals and the return address.
• Each call has its own frame, so two calls to the same function never share a normal local.
• A recursive function has a base case that answers directly, and a recursive case that calls itself with a smaller input.
• Check every recursive function by asking whether the base case is reached, and whether each call moves toward it.
• Factorial and digit sum take O(n) and O(d) time, and O(n) and O(d) stack space. Naive Fibonacci makes about 2^n calls.
• A stack overflow is a crash that comes from too many frames. The usual causes are a missing base case or a call that does not shrink its input.
• Use a loop for simple repeated work. Use recursion when the problem splits into smaller problems of the same shape.