The call stack from the inside

Code in:JavaC#PythonJavaScript

In short: The call stack keeps one frame for every call that has not finished; when recursion goes too deep Python stops the program with RecursionError.

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 function counts them, as in the lesson "Recursion":

def count_products(category):
    total = category.products
    for child in category.children:
        total += count_products(child)
    return total


phones = Category("Phones", 5)
laptops = Category("Laptops", 3)
electronics = Category("Electronics", 2).add(phones, laptops)
kitchen = Category("Kitchen", 6)
home = Category("Home", 4).add(kitchen)
shop = Category("Shop", 0).add(electronics, home)
print("Products: " + str(count_products(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 RecursionError: maximum recursion depth exceeded.

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 count_products 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:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(3))  # 6

Step by step, in words

1. The program calls factorial(3).
2. New memory for factorial with n = 3.
3. 3 is not 1, so the function 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 the program 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:

def count_products(category):
    total = category.products
    for child in category.children:
        total += count_products(child)
    return total

print("Products: " + str(count_products(shop)))

Step by step, in words

1. The program calls count_products(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 4 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 4: 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 count_products 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.

depth = 0
deepest = 0


def count_products(category):
    global depth, deepest
    depth += 1
    deepest = max(deepest, depth)
    total = category.products
    for child in category.children:
        total += count_products(child)
    depth -= 1
    return total


total = count_products(shop)
print(f"{total} products, at most {deepest} frames at once")

Answer

20 products, at most 3 frames at once

20 products, at most 6 frames at once

20 products, at most 2 frames at once

Check

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.

print("Python's limit:", sys.getrecursionlimit())
print(f"Depth 900: {count_products(chain(900))} products")
try:
    print(f"Depth 100000: {count_products(chain(100_000))} products")
except RecursionError as e:
    print(f"Depth 100000: RecursionError: {e}")

Output

Python's limit: 1000
Depth 900: 900 products
Depth 100000: RecursionError: maximum recursion depth exceeded

Python stops already at 1000 frames, long before the real stack runs out. This is a guard, not the end of memory: 900 levels pass, 1000 do not.

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. From there the error falls like any exception: a frame without catch is thrown away and the error keeps going down. That is how the exception from withdrawing money fell through the frames in the lesson "Throwing exceptions":

def withdraw(self, amount):
    if amount > self.balance:
        raise ValueError("Not enough money")
    self.balance -= amount


def pay_rent(account):
    account.withdraw(800)
    print("The rent is paid.")


try:
    pay_rent(Account(500))
except ValueError as e:
    print(f"Declined: {e}")

Step by step, in words

1. The program calls pay_rent for an account with €500.
2. pay_rent calls withdraw(800): a new frame on top.
3. 800 > 500: the method throws an exception with raise.
4. The balance does not change: the frame is thrown away without finishing its lines.
5. pay_rent has no except: "The rent is paid." is not printed, and the frame is thrown away.
6. The except in the program 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.

The idea

The cycle: the base case never comes

Where is the base case of count_products? There is no if. The base case is a category with no subcategories: the loop does not run even once, and the function 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:
    print("Products: " + str(count_products(shop)))
except RecursionError as e:
    print(f"With the cycle: RecursionError: {e}")

Output

With the cycle: RecursionError: maximum recursion depth exceeded

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 function returns the category without going further down;
• nothing further down: no subcategory contains it, and the function returns None.

def find(category, name):
    if category.name == name:
        return category
    for child in category.children:
        found = find(child, name)
        if found is not None:
            return found
    return None


for name in ["Kitchen", "Garden"]:
    found = find(shop, name)
    if found is None:
        print(name + ": no such category")
    else:
        print(f"{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?

def find(category, name):
    if category.name == name:
        return category
    for child in category.children:
        found = find(child, name)
        if found is not None:
            return found
    return 

Check

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 stops with RecursionError. Which line is wrong?

Pick the line with the bug.

1def months(debt, payment):2 if debt == 0:3 return 04 return 1 + months(debt - payment, payment)

Check

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 function path(category, name) that returns the list of names from the root to the category you look for, or None 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 Python the limit is a number of frames: sys.getrecursionlimit() is 1000. sys.setrecursionlimit(100_000) raises the limit, but not the real stack of the process: with deep enough recursion Python crashes without a message. To really get more room you need a thread with a bigger stack (threading.stack_size), and even then the chain from the import can be deeper than that.

The size of a frame. How many frames fit depends on the frame: more parameters and local variables are more bytes. That is why in Node the number of calls before the overflow is not an exact number, while in Python it is, because Python counts frames.

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?

The parameter category, the locals total and child, and the place where the frame below continuesOnly the result it will returnThe whole category tree

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?

1010004

3. "Home" is put under its own "Kitchen" by mistake. Why does the walk overflow the stack instead of giving a wrong sum?

The tree becomes too wideThe sum gets bigger than intOn the path around the cycle every category has a subcategory, so the base case (a category with no children) never comes

4. months(130, 50) should return 3, but it overflows the stack. Why?

The debt goes 80, 30, −20, −70… and is never exactly 0The recursion is too deep for 130payment does not get smaller

5. What does the Python limit measure, and what does the stack limit in Java, C# and JavaScript measure?

Python counts frames (1000), the others measure bytes of memory, so the number of calls depends on the size of a frameBoth measure bytesBoth count frames

Check

Start the lesson over

Related lessons

• Builds on: Lambdas · Threads · Big-O: how the work grows · Space complexity
• Continues in: From recursion to a loop · Fast exponentiation · Binary search tree · DFS: islands and cycles
• Tasks on this topic: Recursion