Skip to content
wannacode

The call stack from the inside

In short: The call stack keeps one frame for every call that has not finished; when recursion goes too deep it runs out and the process dies with StackOverflowException.

Problem

The catalog that takes the page down

The menu of an online shop is a tree: categories, subcategories inside them, a few products in each. Next to the name it says how many products there are, subcategories included: "Electronics (10)". A recursive method counts them, as in the lesson "Recursion":

static int CountProducts(Category category)
{
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}


var phones = new Category("Phones", 5);
var laptops = new Category("Laptops", 3);
var electronics = new Category("Electronics", 2).Add(phones, laptops);
var kitchen = new Category("Kitchen", 6);
var home = new Category("Home", 4).Add(kitchen);
var shop = new Category("Shop", 0).Add(electronics, home);
Console.WriteLine("Products: " + CountProducts(shop));
Output
Products: 20

It works for months. Then two new imports from suppliers arrive. The first puts every new category inside the previous one: the chain is 100,000 levels deep. The second, by mistake, puts "Home" inside its own subcategory "Kitchen". In both cases the page fails with Stack overflow., and the server process dies.

The code is the same, and it is correct. What ran out?

The idea

What one call costs

Every call gets its own memory on the stack. It is called a frame (stack frame) and holds three things:

  • the parameters: here category, the category this call counts;
  • the local variables: total and child, how far the loop has got;
  • the return point: which line of the caller continues when this call finishes.

The frame lives until the call returns. Then it is thrown away and its place is reused. The number of frames alive at once is the depth of the recursion. It is not the number of calls: the walk calls CountProducts 6 times, but there are at most 3 frames at once.

In the recursion lesson you already saw the pile of frames for factorial. Every call has its own n and waits for the answer of the one above it:

static int Factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }
    return n * Factorial(n - 1);
}


Console.WriteLine(Factorial(3));  // 6
Step by step, in words
  1. Main calls Factorial(3).
  2. New memory for Factorial with n = 3.
  3. 3 is not 1, so the method calls Factorial(2) and waits for the answer.
  4. The same again: Factorial(2) calls Factorial(1). Each call has its own n.
  5. n is 1: this is the base case. It returns 1 without calling again.
  6. The answer comes back down: 2 * 1 = 2.
  7. And again: 3 * 2 = 6.
  8. Factorial(3) returns 6 and Main prints it.

See it

The frames of the walk

Now the same with the shop tree. Watch the slots of each frame and the line the frame below is waiting on:

static int CountProducts(Category category)
{
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}


Console.WriteLine("Products: " + CountProducts(shop));
Step by step, in words
  1. Main calls CountProducts(shop). So far the stack holds only its frame.
  2. A new frame: the parameter category = Shop, the local total = 0 and the return point, where to go back when it ends.
  3. The loop reaches child = Electronics and calls itself. The Shop frame stops on line 6 and waits; the new frame remembers that line.
  4. Phones has no subcategories: the loop does not run. That is the base case. 3 frames of the walk are alive at once: the depth is 3.
  5. return 5: the frame is thrown away. Electronics carries on from line 6: total = 2 + 5 = 7.
  6. Laptops takes the same place in the stack and returns 3. total = 7 + 3 = 10.
  7. Electronics returns 10. The Shop frame wakes up where it stopped: total = 10.
  8. Next child: Home, then Kitchen. Again 3 frames, in the same places.
  9. Kitchen returns 6, Home returns 4 + 6 = 10, and Shop gets to 10 + 10 = 20.
  10. 20 products. 6 calls, but never more than 3 frames of the walk at once: the stack grows with the depth of the tree, not with the number of categories.

When "Phones" returns, its frame disappears, and "Laptops" takes the same place. The memory of the walk grows with the longest path in the tree, not with the number of categories. For a chain of 100,000 categories the longest path is 100,000.

Try it

How many frames at once?

Here CountProducts counts how many of its frames are alive (depth) and remembers the largest value (deepest). The tree is the same: Shop, Electronics with Phones and Laptops, Home with Kitchen.

static int depth = 0;
static int deepest = 0;


static int CountProducts(Category category)
{
    depth++;
    deepest = Math.Max(deepest, depth);
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    depth--;
    return total;
}


int total = CountProducts(shop);
Console.WriteLine($"{total} products, at most {deepest} frames at once");
Answer

The idea

Why the stack runs out

The stack is a separate block of memory for each thread, and it does not grow by itself: in Java, C# and Node it is on the order of 1 MB, and Python counts frames and stops at 1000. One frame is small, tens to a hundred bytes, but the chain from the import needs 100,000 frames at once. chain(n) builds such a chain: n categories, each inside the previous one, one product each.

var small = Chain(900);
Console.WriteLine($"Depth 900: {CountProducts(small)} products");
var deep = Chain(100_000);
var worker = new Thread(() =>
{
    try
    {
        Console.WriteLine($"Depth 100000: {CountProducts(deep)} products");
    }
    catch (InsufficientExecutionStackException e)
    {
        Console.WriteLine("Depth 100000: " + e.GetType().Name);
    }
}, 1024 * 1024);
worker.Start();
worker.Join();
Output
Depth 900: 900 products
Depth 100000: InsufficientExecutionStackException

In C# a real overflow cannot be caught: the process prints Stack overflow., a list of frames, and stops, together with the whole server. No catch can save it. That is why the program above does not trigger it for real. The first line of CountProducts is a guard: RuntimeHelpers.EnsureSufficientExecutionStack() throws InsufficientExecutionStackException when the stack is almost full, and that exception can be caught. The walk runs in a thread with a 1 MB stack (the second argument of new Thread), so it behaves the same on every machine: on Linux the main thread has 8 MB and would fit more levels.

static int CountProducts(Category category)
{
    RuntimeHelpers.EnsureSufficientExecutionStack();
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}

The memory the walk needs is O(depth), as in the lesson "Space complexity". In a balanced tree the depth is small. In a chain it is n.

See it

The error falls through every frame

The overflow happens in the top frame, 100,000 levels up. The guard throws InsufficientExecutionStackException, and it falls like any exception: a frame without catch is thrown away and the exception keeps going down. That is how the exception from withdrawing money fell through the frames in the lesson "Throwing exceptions":

public void Withdraw(int amount)
{
    if (amount > Balance)
    {
        throw new ArgumentException("Not enough money");
    }
    Balance -= amount;
}
static void PayRent(Account account)
{
    account.Withdraw(800);
    Console.WriteLine("The rent is paid.");
}


try
{
    PayRent(new Account(500));
}
catch (ArgumentException e)
{
    Console.WriteLine("Declined: " + e.Message);
}
Step by step, in words
  1. Main calls PayRent for an account with €500.
  2. PayRent calls Withdraw(800): a new frame on top.
  3. 800 > 500: the method throws an exception.
  4. The balance does not change: the frame is thrown away without finishing its lines.
  5. PayRent has no catch: "The rent is paid." is not printed, and the frame is thrown away.
  6. The catch in Main catches the exception, and the program continues from here.

When the error reaches catch, all 100,000 frames are already gone and the stack is empty again. That is why the program above carries on and prints. A real StackOverflowException does not fall like this: the process stops on the spot.

The idea

The cycle: the base case never comes

Where is the base case of CountProducts? There is no if. The base case is a category with no subcategories: the loop does not run even once, and the method returns its own products.

The second import put "Home" inside its own "Kitchen". Now the path Shop → Home → Kitchen → Home → Kitchen → … has no end. Every category on it has a subcategory, so the base case never comes:

kitchen.Add(home);
try
{
    Console.WriteLine("Products: " + CountProducts(shop));
}
catch (InsufficientExecutionStackException e)
{
    Console.WriteLine("With the cycle: " + e.GetType().Name);
}
Output
With the cycle: InsufficientExecutionStackException

This is a base case that is never reached. It is there in the code, but the input never leads to it. The tree comes from outside (an import, an API, a database), so the walk has to survive both a deep tree and a circular one. How is in the next lesson, "From recursion to a loop".

The idea

Two base cases

Sometimes there is more than one reason to stop. Find looks for a category by name and has two base cases:

  • found: the name matches, and the method returns the category without going further down;
  • nothing further down: no subcategory contains it, and the method returns null.
static Category? Find(Category category, string name)
{
    if (category.Name == name)
    {
        return category;
    }
    foreach (Category child in category.Children)
    {
        Category? found = Find(child, name);
        if (found != null)
        {
            return found;
        }
    }
    return null;
}


foreach (string name in new[] { "Kitchen", "Garden" })
{
    Category? found = Find(shop, name);
    if (found == null)
    {
        Console.WriteLine(name + ": no such category");
    }
    else
    {
        Console.WriteLine($"{name}: {found.Products} products");
    }
}
Output
Kitchen: 6 products
Garden: no such category

As soon as one child finds the category, the answer goes straight back up through all the frames, without walking the other children.

Try it

Fill in

What does Find return when the category is in none of the subtrees?

static Category? Find(Category category, string name)
{
    if (category.Name == name)
    {
        return category;
    }
    foreach (Category child in category.Children)
    {
        Category? found = Find(child, name);
        if (found != null)
        {
            return found;
        }
    }
    return ;
}

Try it

Find the bug

The shop sells in instalments. Months(150, 50) returns 3 months. Months(130, 50) should also return 3 (€50, €50 and €30), but it kills the process with Stack overflow.. Which line is wrong?

Pick the line with the bug.

Exercise

The breadcrumb

Solve this in your editor.

The path to the category. Above the products the shop shows the path to the category: "Shop > Home > Kitchen". Write a recursive method Path(category, name) that returns the list of names from the root to the category you look for, or null if it is not there. The two base cases are as in Find. Read the name and print the path.

Input
Kitchen
Output
Shop > Home > Kitchen

With the input Garden the output is No such category.

More tasks

  • The deepest category. Write a recursive Depth(category): a category with no children is at depth 1, otherwise it is 1 + the deepest child. For the tree in the lesson it is 3, for the chain from the import it is 100,000.
  • The instalments. Fix Months and run it with 130 and 50, then with 0 and 50. How many frames does each call open?

More precisely

How big the stack is

The stack is not endless, and it is not the same everywhere. The numbers below are defaults, and they can be changed.

More precisely, if you are curious

The size. In .NET the main thread has about 1 MB on Windows, and on Linux whatever the system gives, usually 8 MB. new Thread(work, maxStackSize) gives a new thread its own size. EnsureSufficientExecutionStack looks at how much is left in the stack of the current thread, so the guard works at any size.

The size of a frame. How many frames fit depends on the frame: more parameters and local variables are more bytes. The JIT compiler can make a frame smaller, so the number of calls before the overflow is not an exact number and changes between runs.

The tree and object memory. The categories themselves are not on the stack. They are objects in object memory (the heap), and a frame holds only a reference to one of them. That is why 100,000 categories fit in memory without trouble, while 100,000 frames at once do not.

Returning. The return point is the address of the instruction where the caller continues. On the processor this is literally an address in memory, written into the frame. The scene shows it as a line number.

Test

Check yourself

1. What does the frame of the call for the category "Home" hold?
2. The catalog has 1000 categories, and the longest path from "Shop" to the deepest one is 4 categories. How many frames of the walk exist at once, at most?
3. "Home" is put under its own "Kitchen" by mistake. Why does the walk overflow the stack instead of giving a wrong sum?
4. months(130, 50) should return 3, but it overflows the stack. Why?
5. What does the Python limit measure, and what does the stack limit in Java, C# and JavaScript measure?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·