Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture VI of XIV

Lecture VI · Data Structures & Algorithms

Recursion and the call stack

Two lectures ago we built a stack: push at the top, pop from the top, last in first out. Today the surprise is that you have been standing on one this whole time. Every function call your program makes lives on a stack the machine keeps for itself, and once you can see that stack, recursion stops being spooky. It is just a function trusting a smaller copy of itself, and the machine keeping the bookkeeping straight.

The recursive leap of faith

Start with a habit of mind, not a line of code. You already know how to prove a statement by induction: show it holds for the smallest case, then show that if it holds for n - 1 it holds for n. A recursive function is that same argument, except you can run it. It has a base case, the smallest input you can answer outright, and a recursive case, which answers a bigger input by asking the same function about a smaller one and building on the reply.

The move that trips everyone at first is the recursive case, because it feels circular. You are writing sum_to(n) and, halfway through, you write sum_to(n - 1) as if it already worked. It is not finished. How dare you call it? This is the leap of faith, and it is exactly the inductive hypothesis wearing work clothes. You do not trace sum_to(n - 1) all the way down in your head. You assume it returns the right answer for the smaller input, and you ask only one question: given a correct answer for n - 1, can I produce a correct answer for n? For a sum, yes: add n to it.

def sum_to(n):
    if n == 0:          # base case: the sum of nothing is 0
        return 0
    return n + sum_to(n - 1)   # trust the smaller sum, then add n

Two obligations come with the faith, and they are the whole discipline. First, the base case has to actually stop the descent. Second, every recursive call has to move toward that base case, on inputs that genuinely shrink. Get those two right and the leap always lands. Get them wrong and you fall forever, which, as we are about to see, is a very concrete kind of falling.

What the machine really does: the call stack

The leap of faith is how you reason about recursion. Now let us watch what the machine actually does, because it is not magic and it is not circular. When a function is called, the machine sets aside a small block of memory called a stack frame: a scratchpad holding that call’s arguments, its local variables, and a note saying where to return when it finishes. Call a second function from inside the first and a second frame goes on top. That collection of frames is the call stack, and it obeys the exact contract from Lecture IV. The most recent call is on top; it must finish and be popped before the call beneath it can resume. Last in, first out. The call stack is a stack, the same ADT we built by hand, except the machine pushes and pops it for you on every call and every return.

So a recursive call is nothing exotic. fib(5) calls fib(4), which pushes a frame; that call has not returned, so fib(5)’s frame just waits underneath, holding its place. The stack grows as the recursion descends and shrinks as answers come back. Watch it happen. In the plate below, step through fib(n) one event at a time: the left column is the live call stack, pushing a frame on every call and popping it on every return, with the top frame (the call running right now) lit in ochre. Beside it, the recursion tree unfolds node by node, each subproblem turning green the instant it returns its value.

Call stack · deepest point

fib(5)
fib(4)
fib(3)
fib(2)
fib(1)

Recursion tree · fib(5), fully returned

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

fib(5) = 5 · 15 calls in all · stack 4 frames deep at most. Enable JavaScript to step the push and pop one event at a time.

Plate I The call stack, animated. Step through a recursive fib(n): frames push and pop in the left column (the running call is ochre), while the recursion tree unfolds and settles beside it (returned calls turn green). Watch the stack depth rise and fall, and watch the same small subproblems get computed again and again. Press Step, or Play, and drag n from 3 to 6.

Two things are worth staring at. The stack never gets deeper than the longest path from the root down to a base case: for fib(5) that is five frames, not fifteen, even though fifteen calls happen in total. Depth is about the path, not the count. And the tree is doing an enormous amount of repeated work: the same fib(2) subtree is rebuilt over and over, from scratch, because no call remembers what any other call already figured out. Hold that thought. It is the crack that the next lecture pries wide open.

Fibonacci, and the tree that explodes

Here is the naive Fibonacci in full, the canonical trace worth knowing by heart:

def fib(n):
    if n < 2:                     # base cases: fib(0) = 0, fib(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)   # recursive case: two smaller calls

It is a direct transcription of the definition, and as an inductive argument it is flawless. Both base cases stop the descent; both recursive calls shrink n. Read it with the leap of faith and it is obviously correct. Read it with the call stack in mind and it is obviously a disaster.

The trouble is the branching. Each non-base call spawns two more, and neither knows the other exists, so the tree of calls fans out and the same subproblems get recomputed a staggering number of times. Do not take my word for the growth. Let us count it.

python runs in your browser · first run downloads ~240 kb
Plate II Instrument fib and count its own calls. Each call bumps a counter; the loop resets it and prints how many calls each fib(n) costs. Press Run and read the last column: it grows like fib itself, which is to say exponentially.

Run it and look at the last column. Computing fib(10) takes 177 calls; fib(15), 1973; fib(20), if you dare, over thirteen thousand. The call count for fib(n) is itself about fib(n), and Fibonacci grows exponentially, roughly like 1.618n1.618^n. So the running time of this innocent four-line function is exponential in nn. It is not that the recursion is wrong; it computes the right number every time. It is that it computes the right subanswers an exponential number of times, throwing each one away the moment it is used.

You should find fib(2) computed three times, fib(1) five times, and fib(0) three times, for fifteen calls in all to produce a single number. Every one of those repeats is pure waste, an answer we already knew and refused to keep. I am going to leave it there, unfixed, on purpose. The cure has a name, memoizing the repeated subproblems, and it turns this exponential back into a straight line. But that is the whole subject of the next lecture, so for now just register the diagnosis: recursion is honest and elegant here, and ruinously slow, and the slowness is repeated work you can see in the tree.

Euclid, and the recursion that shrinks fast

Lest recursion take the blame for Fibonacci’s sins, meet the counterexample: an algorithm from around 300 BCE that is recursive to its bones and breathtakingly fast. Euclid’s algorithm finds the greatest common divisor of two numbers, and its whole idea fits in a sentence. The gcd⁡\gcd of aa and bb is the same as the gcd⁡\gcd of bb and the remainder of aa divided by bb, and the gcd⁡\gcd of any number with 0 is that number.

def gcd(a, b):
    if b == 0:            # base case: gcd(a, 0) is a
        return a
    return gcd(b, a % b)  # recursive case: replace (a, b) with (b, a mod b)

Look at how differently this recurses. There is no branching: one call, one smaller call, a single unbranched chain down to the base. So the call stack goes down in a straight line and comes straight back up, with no repeated work to speak of. And it shrinks fast. Each step replaces b with a % b, a remainder, which is strictly smaller, and in fact the numbers fall so quickly that the whole thing finishes in a number of steps proportional to the digits of the input, not its size. gcd(1071, 462) is done in a handful of calls. This is the good kind of recursion: it provably terminates, because a % b is always smaller than b and a strictly decreasing count of non-negative integers cannot go forever, and it gets to the base case in a hurry.

python runs in your browser · first run downloads ~240 kb
Plate III Trace Euclid by hand. Press Trace, then Step through gcd(1071, 462): watch the arguments march down (1071, 462) then (462, 147) then (147, 21) then (21, 0), one unbranched frame at a time, and the answer climb back. Compare this tidy chain to Fibonacci's exploding tree.

Set the two traces side by side and the lesson writes itself. Both are honest inductive arguments. Fibonacci branches and rebuilds the same subproblems, so its tree explodes; Euclid recurses once and shrinks hard, so its chain is short. When you write a recursion, the question is never just “does it terminate,” it is “what shape is the tree, and does any subproblem get solved twice.” That single question separates the elegant recursions from the ruinous ones.

Recursion on structures, not just numbers

Everything so far has recursed on a number: n goes down to n - 1, or a pair of integers shrinks toward zero. That is the easiest place to start and the worst place to stop, because it leaves you with the impression that recursion is a fancy way to count down. It is not. Recursion is for shapes that contain smaller copies of themselves, and numbers are only the dullest example.

Here is a shape that is genuinely recursive. A nested list is a list whose items are either plain values or other nested lists. Read that definition again and notice that it defines the thing in terms of itself, which is your cue. Any question you want to ask about a nested list has an answer with exactly two parts: what to do with a plain value, and how to combine the answers from the sublists. That is a base case and a recursive case, handed to you by the data.

def total(x):
    if isinstance(x, list):
        s = 0
        for item in x:
            s += total(item)   # trust the smaller total
        return s
    return x                   # a plain value is its own total

Look at how little thinking that took. I never asked how deep the nesting goes, and I never wrote a counter. The structure is recursive, so the code is recursive, and the two match so closely that the code is almost a restatement of the definition. This is what people mean when they say recursion is elegant: not that it is clever, but that when the data has this shape, the recursive solution is the one that stops being clever.

Notice also that the recursion tree here is not a metaphor. It is the list. Each recursive call handles one sublist, so the shape of the call tree is exactly the shape of the nesting, and the stack gets as deep as the nesting is deep, never deeper. If your data is three brackets deep, the stack is three frames deep, no matter how many thousands of items are inside.

python runs in your browser · first run downloads ~240 kb
Plate IV Recursion on a shape. total walks a nested list and adds everything it finds; depth measures how many brackets deep the nesting goes. Press Run, then edit nest to nest something deeper and run again. The stack depth follows the bracket depth, not the item count.

Tail shape, non-tail shape, and what Python does about it

Two recursions can compute the same answer and put the machine under completely different pressure, and the difference is one question: when the recursive call returns, is there any work left to do in this frame?

def pending(n):
    if n == 0:
        return 0
    return n + pending(n - 1)   # an addition is still owed

def carried(n, acc=0):
    if n == 0:
        return acc
    return carried(n - 1, acc + n)   # nothing is owed

In pending, the frame has to stay alive: it has handed off a subproblem, and when the answer comes back it still owes an addition. That waiting is the entire reason a stack exists. In carried, the addition has already happened before the call, and the recursive call’s answer is simply this call’s answer, passed straight up untouched. A call in that position is called a tail call, and the frame that makes it has nothing to contribute afterwards. It is dead weight holding a place in line for no reason.

Some languages notice. Scheme and its relatives are required to notice: a tail call is compiled into a jump that reuses the current frame, so a tail-recursive loop runs in constant stack space and you can write a million-step recursion without a thought. Python is not one of those languages. It has no tail-call optimisation, and Guido van Rossum has said publicly that this is on purpose, because rewriting the stack would erase the traceback that tells you where you were when something went wrong. So in Python the tail shape is a way of thinking, not a way of saving memory. Measure it and see.

python runs in your browser · first run downloads ~240 kb
Plate V The depth meter. The same sum written non-tail, tail, and as a loop, each instrumented with enter/leave counters that record the deepest the stack ever got. Press Run: the two recursions both reach 51 frames, because CPython and MicroPython alike keep the tail frame alive, while the loop never leaves depth 1. Raise 50 and watch which one notices.

Both recursions peak at fifty-one frames. The tail version did not save a single one, which is exactly the point: in Python, writing a recursion in tail form buys you clarity and nothing else. What it does buy, and this is worth keeping, is a trivially mechanical rewrite into a loop. A tail recursion whose only pending work is the call itself turns into a while loop by rote: the arguments become variables, the recursive call becomes an assignment to those variables, the base case becomes the loop condition. If you can get a recursion into tail form, you can get it onto the flat ground of a loop, and then the stack limit stops being your problem.

Two functions that need each other

Recursion does not have to be a function calling itself by name. It only has to be a cycle of calls that shrinks its input. The smallest interesting case is two functions defined in terms of each other, which we call mutual recursion.

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

Neither function is recursive if you read it alone. Together they descend one step at a time, alternating, until somebody hits zero and answers outright. The stack does something rather pretty here: it fills with frames from two different functions taken in turns, and the answer travels back up through both of them. The two obligations have not changed. There are base cases, in both functions, and n genuinely shrinks on every hop, so the descent terminates.

This is a toy, but the pattern is not. Any grammar with mutually referring rules gives you mutually recursive code for free, and that is how nearly every real parser is written: a function for expressions that calls the one for terms, which calls the one for factors, which calls back into expressions when it meets a parenthesis. The recursion follows the grammar the same way total followed the brackets.

python runs in your browser · first run downloads ~240 kb
Plate VI Mutual recursion, with a trail. is_even and is_odd take turns down the stack; the trail list records each frame as it opens. Press Run and read the last line: even(6), odd(5), even(4) and so on, one alternating step per level, all the way to a base case.

When recursion bites

Recursion is a way of thinking, but it runs on a finite machine, and the finiteness bites in one specific place: the call stack is not bottomless. Every waiting frame costs real memory, and language runtimes cap how deep the stack may go. In CPython the default limit is around one thousand nested calls; blow past it and you get a RecursionError rather than a crash, which is Python being polite about what would otherwise be a stack overflow. The MicroPython interpreter running these plates has a shallower limit still, which is worth knowing before you point a deep recursion at it.

That means the base case is not a nicety, it is a safety rail. Forget it, or write a recursive call that does not actually shrink the input, and you do not get a wrong answer, you get a descent with no floor: frame after frame, forever, until the stack fills and the runtime cuts you off. The two obligations from the start of the hour, a reachable base case and inputs that genuinely move toward it, are exactly the two things that keep the stack finite.

It is worth being precise about what a RecursionError actually reports, because students routinely misread it. It is not the operating system telling you that memory ran out. It is Python counting. The interpreter keeps a tally of how many frames are currently open, compares it against sys.getrecursionlimit() (a thousand by default), and raises a perfectly ordinary Python exception the moment you exceed it. That limit is a guard rail placed well before the real hardware stack would be exhausted, precisely so you get a catchable exception with a readable traceback instead of a segmentation fault. You can raise the limit with sys.setrecursionlimit, and you almost never should: past a certain point the guard rail is the only thing standing between you and a genuine crash that Python cannot turn into an exception.

Read that error, then, as a diagnosis rather than a resource complaint. It says one of two things happened. Either your recursion is correct but too deep for the default limit, in which case the fix is usually a loop or an explicit stack. Or, much more often, your recursion has no floor: the base case is missing, or it is present but the steps stride right past it. The second failure is the sneaky one, because the code contains a base case and looks fine. countdown(n) returning at n == 0 and recursing on n - 2 is perfectly correct for even inputs and falls forever on odd ones. The base case has to be reachable from every input you allow, not merely present in the source.

python runs in your browser · first run downloads ~240 kb
Plate VII Falling with no floor. Two descents that never bottom out, each caught so the page survives: one with no base case at all, one whose base case is stepped over from an odd start. Press Run and read the exception name and message. This interpreter is MicroPython, so it says RuntimeError where CPython says RecursionError; the mechanism, a frame counter tripping a limit, is the same.

And sometimes the honest move is to not recurse at all. A recursion that is a single unbranched chain, like sum_to or Euclid or a factorial, does the same work as a plain loop, and the loop keeps the stack flat: one frame, not n of them. sum_to(1000) as written above will strain a shallow stack, while sum(range(1001)) will not blink. So the rule of thumb is this. Reach for recursion when the problem is recursive, when it naturally breaks into smaller copies of itself, a tree to walk, a structure to divide and conquer. When the recursion is just counting down a straight line, a loop is often the plainer, safer tool. Recursion is a way to describe a computation; it is not always the way to run one.

Turning a recursion into an explicit stack

That leaves an obvious question. A straight-line recursion turns into a loop, we just said so. But what about a branching one, a walk over a tree, where each call has two subproblems and has to come back for the second after finishing the first? A plain loop cannot remember where to come back to. So what do you do when the recursion genuinely branches and the depth is genuinely too much for the stack?

You take the machine’s job away from it. The call stack was only ever doing one thing for you: remembering the subproblems you have not gotten to yet. That is a stack of pending work, and we know how to build one of those. We built one by hand in Lecture IV. So the conversion is mechanical: replace the machine’s stack with a list of your own, push the subproblems you have not handled, and loop until the list is empty.

def preorder(root):
    if root is None:
        return []
    out, todo = [], [root]        # todo is our stack of pending nodes
    while todo:
        node = todo.pop()         # the most recent pending node, LIFO
        out.append(node.data)
        if node.right is not None:
            todo.append(node.right)   # pushed first, so popped second
        if node.left is not None:
            todo.append(node.left)    # pushed last, so visited next
    return out

Compare that with the three-line recursive version and notice what has and has not changed. The order of the output is identical, because the last-in-first-out discipline of the list reproduces exactly the last-in-first-out discipline of the frames. What changed is where the pending work lives: in a Python list on the heap, which can grow to millions of entries, rather than in interpreter frames, which cannot. The push-right-then-left ordering is the one detail worth pausing on. We want the left subtree visited first, and a stack hands back the most recent thing, so the left child has to go on last.

This is the deepest lesson of the hour, and it is why a lecture on recursion belongs immediately after a lecture on stacks. Recursion is not a separate mechanism. It is a stack of pending work with the pushing and popping written implicitly, and any recursion at all can be rewritten with that stack made explicit. What you give up is the elegance. What you buy is control, and a depth bounded by memory instead of by an interpreter’s frame counter.

Exercises

  1. Write sum_to(n) recursively (sum of the integers from 0 through n), then rewrite it as a while loop that keeps a running total. State, in one sentence, how deep the call stack gets in each version for sum_to(100). This is the recursion-versus-loop trade-off made concrete.

  2. A string is a palindrome if it reads the same forwards and backwards. Write is_palindrome(s) recursively: give the base case (what is the smallest string you can judge at a glance?), then compare the two ends and recurse on the middle. Name the input that shrinks and confirm it reaches the base case.

  3. Return to Plate I and set n to 6. Without running the counter, use the tree to argue how many total calls fib(6) makes, and how many of them are calls to fib(1). Then explain in one sentence why memoizing would collapse that count, foreshadowing next lecture.

  4. The main event. Write factorial(n) recursively so the checks go green: a base case of 0! = 1, and a recursive case that trusts factorial(n - 1) and multiplies by n. The leap of faith is the whole trick: assume the smaller factorial is correct, and you are one multiplication from done.

    The checks · run against your code

    # factorial(0) is 1
    assert factorial(0) == 1
    # factorial(1) is 1
    assert factorial(1) == 1
    # factorial(5) is 120
    assert factorial(5) == 120
    # factorial(7) is 5040
    assert factorial(7) == 5040
    # it recurses rather than looping to a wrong answer on a bigger n
    assert factorial(10) == 3628800
    python runs in your browser · first run downloads ~240 kb
    Plate VIII Write the recursion, watch the checks. Fill in factorial with a base case and a recursive case that leans on the smaller call. Press Run; then press Trace and Step to watch the stack of factorial frames build up and unwind.
    Hint one

    Two lines do it. The base case answers the smallest input outright: if n == 0: return 1. Everything else is the recursive case.

    Hint two

    For the recursive case, take the leap of faith: assume factorial(n - 1) already returns the right answer for the smaller input, and ask what you owe on top of it. For a factorial, one multiplication by n.

    The solution

    A base case and a single trusting recursive call. Each frame waits on the one above it, so the multiplications happen on the way back up, 1 then times 1, times 2, times 3, and so on.

    def factorial(n):
      if n == 0:              # base case
          return 1
      return n * factorial(n - 1)   # trust the smaller factorial

    Press Trace on the plate to see it: the stack climbs to n frames deep as the calls descend, then pops one at a time as each multiplication resolves and the answer travels back to the top.

  5. Recursion on a shape. Write flatten(xs), which takes a list whose items are numbers or lists (nested to any depth) and returns one flat list of the numbers in left-to-right order. Do not count anything and do not ask how deep the nesting goes; let the structure tell you where the two cases are. The checks include the two inputs people forget, the empty list and a list whose only contents are empty lists.

    The checks · run against your code

    # an already-flat list comes back unchanged
    assert flatten([1, 2, 3]) == [1, 2, 3]
    # one level of nesting is opened up
    assert flatten([1, [2, 3], 4]) == [1, 2, 3, 4]
    # nesting to any depth is opened up
    assert flatten([1, [2, [3, [4, [5]]]]]) == [1, 2, 3, 4, 5]
    # empty lists vanish rather than leaving holes
    assert flatten([[], [1, []], []]) == [1]
    # the empty list flattens to the empty list
    assert flatten([]) == []
    # the input is not modified along the way
    src = [1, [2, 3]]
    out = flatten(src)
    assert src == [1, [2, 3]]
    python runs in your browser · first run downloads ~240 kb
    Plate IX Flatten, graded. The recursion follows the brackets: a plain value contributes itself, a sublist contributes its own flattening. Run to grade against six checks, including the empty list and nesting five deep.
    Hint one

    Start an empty result list, then walk the items of xs one at a time. For each item, ask the only question that matters: isinstance(item, list). The two answers are your two cases.

    Hint two

    If the item is not a list, append it. If it is, take the leap of faith: flatten(item) already returns a flat list of that sublist’s numbers, so all you owe is to tack that list onto the end of yours. The method for tacking a whole list onto the end is extend, not append; append would nest it right back up.

    The solution

    One loop, one question per item, and the recursive call does all the descending:

    def flatten(xs):
      out = []
      for item in xs:
          if isinstance(item, list):
              out.extend(flatten(item))   # trust the smaller flattening
          else:
              out.append(item)
      return out

    There is no explicit base case here, and that surprises people. The base case is hiding in the loop: when xs is empty, the loop body never runs and the empty list comes straight back. That is why flatten([]) works without a special line, and why the empty-sublist check passes for free. Notice too that the stack only ever gets as deep as the nesting, so a flat list of a million numbers costs exactly one frame.

  6. Two questions about a tree. Implement height(node), the number of nodes on the longest path from the root down to a leaf, and tree_sum(node), the total of every value in the tree. Both take a Node or None, and in both cases the empty tree is the base case. This is the branching recursion from the start of the lecture, now with you writing it: each call has two subproblems, and it has to combine their two answers rather than pass one along.

    The checks · run against your code

    # the empty tree is the base case for both
    assert height(None) == 0
    assert tree_sum(None) == 0
    # a lone leaf is one node tall and sums to itself
    assert height(Node(5)) == 1
    assert tree_sum(Node(5)) == 5
    # height counts the LONGEST path, not the number of nodes
    assert height(t) == 3
    # every node is counted exactly once
    assert tree_sum(t) == 26
    # a lopsided chain is as tall as it is long
    chain = Node(1, None, Node(2, None, Node(3)))
    assert height(chain) == 3
    assert tree_sum(chain) == 6
    python runs in your browser · first run downloads ~240 kb
    Plate X Height and sum, graded. The empty tree answers 0 for both; every other node combines the answers from its two children. Press Run to grade, and note that visualize draws the tree from the left/right attributes so you can check your reasoning against the picture.
    Hint one

    Both functions open the same way: if node is None: return 0. An empty tree has no nodes on any path and no values to add up, so zero is the honest answer to both questions.

    Hint two

    For the recursive case, assume both child calls are already correct. tree_sum owes an addition: this node’s data plus the two subtotals. height owes a choice and then a step: take the larger of the two child heights, because a path can only go down one side, then add 1 for standing on this node.

    The solution

    Same skeleton, different combine step, which is the whole difference between the two questions:

    def height(node):
      if node is None:
          return 0
      return 1 + max(height(node.left), height(node.right))
    
    def tree_sum(node):
      if node is None:
          return 0
      return node.data + tree_sum(node.left) + tree_sum(node.right)

    Every node is visited exactly once by each function, so both are O(n)O(n) in the number of nodes, and the stack gets as deep as the tree is tall. That last clause is why balanced trees will matter so much later: a balanced tree of a million nodes is about twenty frames deep, while the same million nodes wired into a single leaning chain is a million frames deep, which is to say a RecursionError.

  7. The main event, part two. Write preorder(root) so it returns the data of every node in root, left, right order, without recursing. Keep your own stack: a plain Python list, pushed with append and popped with pop, holding the nodes you have not visited yet. Loop until it is empty. This is the conversion from the section above, done by hand, and it is the exercise that proves recursion and stacks are the same thing wearing different clothes.

    The checks · run against your code

    # the empty tree gives the empty list
    assert preorder(None) == []
    # a lone node gives one value
    assert preorder(Node(5)) == [5]
    # root, then all of the left subtree, then all of the right
    assert preorder(t) == [4, 2, 1, 3, 7, 9]
    # a left-leaning chain comes out top down
    left_chain = Node(1, Node(2, Node(3)))
    assert preorder(left_chain) == [1, 2, 3]
    # the result is a list of the data, not of the nodes
    assert isinstance(preorder(t), list)
    assert preorder(Node(5))[0] == 5
    python runs in your browser · first run downloads ~240 kb
    Plate XI Recursion, made explicit. preorder must produce the same order as the recursive walk while keeping its own list of pending nodes. Run to grade against the empty tree, a lone node, a lopsided chain, and the six-node tree from the previous exercise.
    Hint one

    Handle root is None first and return the empty list. Otherwise start with two lists: out, empty, for the answer, and todo, holding just the root, for the pending work. Then loop while todo:.

    Hint two

    Each pass, pop a node, record its data, and push its children. The order of the two pushes is the whole puzzle. A stack returns the most recent thing you gave it, and you want the left child handled next, so push the right child first and the left child second. Push only children that are not None, or write the check when you pop instead; just pick one and be consistent.

    The solution

    The machine’s stack, rebuilt in a list, doing exactly the job the frames were doing:

    def preorder(root):
      if root is None:
          return []
      out, todo = [], [root]
      while todo:
          node = todo.pop()
          out.append(node.data)
          if node.right is not None:
              todo.append(node.right)
          if node.left is not None:
              todo.append(node.left)
      return out

    Trace it on the six-node tree and watch todo breathe: it holds 4, then 2 and 7, then 1, 3 and 7, and so on, never more than the height of the tree plus a little. That is the same amount of pending work the recursive version was holding in frames, which is the point. If you reverse the two pushes you get 4, 7, 9, 2, 3, 1, a perfectly valid walk that visits the right subtree first, and the checks will tell you about it immediately.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.