Recursion to iteration in Python: tail recursion

Problem

The tree comes from outside

In the lesson "The call stack from the inside" the catalog walk failed in two places: the chain from the import was 100,000 levels deep, and another import closed a cycle. A big stack is not a fix. sys.setrecursionlimit only moves the limit: the next import can be deeper, and the real stack of the process runs out without a message.

The tree comes from outside: from a supplier, from an API, from a database. You cannot promise how deep it is. You need a walk whose memory does not depend on the call stack.

The idea

Tail recursion

Start with a simpler task. Above a product the shop shows the level of its category. The level is counted up through the parents until you reach the root:

def level_of(category, level):
    if category.parent is None:
        return level
    return level_of(category.parent, level + 1)

Here the recursive call is the last thing the function does: its result is returned directly, with no + 1 and no loop after it. Such a call is a tail call, and the recursion is tail recursion. After it the frame has nothing more to remember. A language that knows this can reuse the frame instead of adding a new one: the stack does not grow.

But:

Java does not do it. The JVM keeps every frame.
The C# compiler does not do it. The JIT compiler sometimes does it in optimized code, but it is not promised: in our test with .NET 10 in Release the stack still overflowed.
Python does not do it on purpose: Guido van Rossum is against it, because the traceback would lose frames.
JavaScript must do it according to the standard (ES2015, in strict mode). In practice only Safari does. V8 (Chrome, Node) and Firefox do not.

That is why tail recursion fails on the chain from the import too:

last = chain(100_000)
while last.children:
    last = last.children[0]
try:
    print("Recursion: level " + str(level_of(last, 0)))
except RecursionError as e:
    print(f"Recursion: RecursionError: {e}")
print("Loop: level " + str(level_of_loop(last)))

Recursion: RecursionError: maximum recursion depth exceeded
Loop: level 99999

The idea

The tail call becomes while

Tail recursion turns into a loop mechanically, by three rules:

the parameters become variables: category and level;
the call becomes an assignment: instead of calling yourself with the new values, you put them into the variables and start over;
the base case becomes the end condition of the loop: "no parent" stops while.

def level_of_loop(category):
    level = 0
    while category.parent is not None:
        category = category.parent
        level += 1
    return level

This is the bottom line in the output above: the loop gets to level 99,999 with one frame. Recursion and the loop take the same number of steps, one per level. The only difference is where the memory sits.

The idea

The walk is not a tail call

count_products from the previous lesson is not tail recursive. After every call there is work: total += and the next child in the loop. That is why the frames are needed. What did they really hold? The categories it has not got to yet.

A loop can hold that itself, in its own stack: a list of the categories still to come. You take the top one, add its products and put its children on top. The sum is one variable, because adding does not depend on the order.

def count_products(root):
    total = 0
    stack = [root]
    while stack:
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total


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

Products: 20

A list is a stack: append and extend put at the end, pop() takes from the end. How they work inside is in the lesson "Stack and queue".

See it

Your own stack, step by step

def count_products(root):
    total = 0
    stack = [root]
    while stack:
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total

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

Step by step, in words

The stack is a list in object memory (the heap), not the call stack. The root goes in first.
pop takes the top one: Shop. Its children go on top: Electronics, then Home.
Next comes Home, not Electronics: a stack gives back the last thing put in. total = 4, and Kitchen goes in.
Kitchen has no children: nothing goes in. total = 10.
Only now Electronics: total = 12. Phones and Laptops go in.
Laptops (15), then Phones (20).
The stack is empty: the loop stops and returns 20. The stack never held more than 2 categories. The order, though, is Shop, Home, Kitchen, Electronics, Laptops, Phones: not the order of the recursion.

Your own stack is an ordinary object in object memory (the heap). It grows as needed and is limited by all of memory, not by 1 MB. And the numbers in the tree show that the order is different.

Try it

Predict the order

The same walk, but it prints the name of each category as soon as it takes it off the stack:

def print_order(root):
    stack = [root]
    while stack:
        category = stack.pop()
        print(category.name)
        stack.extend(category.children)


print_order(shop)

Answer

Shop
Electronics
Home
Phones
Laptops
Kitchen

Shop
Home
Kitchen
Electronics
Laptops
Phones

Shop
Electronics
Phones
Laptops
Home
Kitchen

The idea

The order of the recursion: children in reverse

For the sum the order does not matter. For the menu it does: "Home" must not come before "Electronics". Recursion visits the parent first, then the children from left to right (pre-order). With your own stack the same order comes out when you push the children in reverse: the last child goes in first and comes out last.

The menu also needs indentation. With recursion the level would be a parameter, that is, in the frame. Now there is no frame, so the stack holds pairs: the category and its level. What the frame held, your stack holds now.

def print_menu(root):
    stack = [(root, 0)]
    while stack:
        category, level = stack.pop()
        print("  " * level + category.name)
        for child in reversed(category.children):
            stack.append((child, level + 1))


print_menu(shop)

Shop
  Electronics
    Phones
    Laptops
  Home
    Kitchen

The stack holds tuples (category, level). reversed() reads the list from the back, without copying it.

See it

The deep tree gets through

The chain from the import, 100,000 levels, with the walk from the lesson:

deep = chain(100_000)
print(f"Depth 100000: {count_products(deep)} products")

Depth 100000: 100000 products

In all four languages, without a thread with a big stack and without touching any limits.

There is no Bench here, on purpose. Recursion and the loop do the same number of operations: one per category, O(n). The curves would be the same. The difference is in memory: recursion keeps up to depth frames on the small stack, the loop keeps the waiting categories on the heap. In a wide tree your own stack can get big (all the waiting siblings), but its room is all of memory.

The idea

A cycle needs memory of what was seen

Your own stack does not save you from a cycle. If "Home" is in "Kitchen" and "Kitchen" is in "Home", the two take turns in the stack forever. The stack does not even grow, so nothing overflows and nothing is thrown: the page simply hangs. That is worse than the error.

The fix is a set of the categories already seen. Before you walk a category, check whether it is already in the set:

def count_products(root):
    total = 0
    seen = set()
    stack = [root]
    while stack:
        category = stack.pop()
        if category in seen:
            print("Skipping " + category.name + ": already visited")
            continue
        seen.add(category)
        total += category.products
        stack.extend(category.children)
    return total


kitchen.add(home)
print("Products: " + str(count_products(shop)))

Skipping Home: already visited
Products: 20

An object without __eq__ and __hash__ is compared by identity: the set holds the categories themselves, not their names. The same set saves the recursion too: count_products with a "seen" parameter stops the cycle. Against depth, though, only the loop helps.

Try it

Put the lines in order

Put the walk with its own stack in order:

category = stack.pop()
while stack:
return total
def count_products(root):
stack = [root]
total = 0
total += category.products
stack.extend(category.children)

Try it

Fill in

When does the loop stop?

def count_products(root):
    total = 0
    stack = [root]
    while :
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total

Exercise

The deepest level

Solve this in your editor.

How deep the catalog is. The import hangs its chain under "Kitchen". Read how many levels the chain has, attach it and print how many categories there are in total and what the deepest level is (Shop is at level 0). No recursion: a stack of pairs of category and level, as in the menu.

Categories: 100006
Deepest level: 100002

More tasks

The breadcrumb without recursion. Rewrite path from the previous lesson with a loop up through the parents. The list is filled from the back.
The menu with the product counts. Print the menu, but next to each category the sum with its subcategories. Hint: the parent's sum is ready only after its children, so with a loop every category goes into the stack twice: once "open" and once "sum".

More precisely

The stack in each language

A stack is written differently in each language, and not every stack is a good choice.

More precisely, if you are curious

Python: a list is a fast stack (append and pop() at the end are O(1)). For a queue use collections.deque: pop(0) on a list is O(n).
A generator with yield from makes the recursive walk short, but there are still frames under it: depth still hits the limit of 1000.

Trampoline. The function does not call itself, but returns "what to call next", and a loop outside calls it. This way tail recursion runs without a growing stack even in languages without tail calls. It works, but a loop written directly is clearer.

A queue instead of a stack. If you use a queue (FIFO) instead of a stack, the walk goes through the tree level by level: Shop, then Electronics and Home, then Phones, Laptops and Kitchen. This is breadth-first search (BFS). It finds the shortest path in a graph, and you will meet it in the graphs module.

Test

Check yourself

1. Which of these calls is a tail call?return level_of(category.parent, level + 1);return 1 + months(debt - payment, payment);total += count_products(child);

A tail call is a call with nothing left to do after it: its result is returned directly. With total += and with 1 + the caller still has work, so its frame is needed.

2. Which of the four languages turns tail recursion into a loop, so that the stack does not grow?Only PythonNone in practice: Java, C# and Python do not, and the JavaScript standard asks for it, but V8 (Node, Chrome) does not do itAll of them, when the call is last

3. Why does the walk with its own stack get through the chain of 100,000 levels, while recursion does not?Its own stack holds only one category at a timeThe loop does fewer operationsIts own stack is an object in object memory and grows as needed, while the function has a single frame

4. The children of a category go into your own stack in their order: Phones, then Laptops. Which comes out first?Laptops: a stack gives back the last thing put inPhones: it is firstIt depends on the language

5. What happens if the walk with its own stack meets a cycle (Home → Kitchen → Home) and does not remember the categories it has seen?It spins forever, without an error: Home and Kitchen take turns in the stackIt throws StackOverflowErrorIt returns a wrong sum and stops

From recursion to a loop

Cookies