What the Machine Is Holding While It Waits

Last timeWhere the Recursion Stops

Every unfinished call is being held somewhere while it waits for the one inside it, and the pile of them is the memory cost nobody writes down when they write the three lines.

What is still outstanding

The previous two lessons described recursion as a claim and never mentioned

the machine. The machine has an opinion about it.

When a method calls itself, the outer call does not finish. It is partway

through, it has local values it is in the middle of using, and it has a place

it intends to continue from once the inner call hands something back. All of

that has to be kept somewhere, because the inner call is about to do the same

thing and will need its own copies of everything.

So while a recursion runs, there is a pile of unfinished calls, each waiting

for the one below it. Adding a list of a thousand numbers in the style of the

first lesson means a thousand outstanding calls at the deepest moment, each

holding its own first item and its own intention to add that item to whatever

comes back.

FIG 1What is held during a sum of four numbers

step	step	the call being entered or finished	calls held	what each is waiting to do
1	1	total of [4, 8, 15, 16]	1	add 4 to what comes back
2	2	total of [8, 15, 16]	2	add 4, then add 8
3	3	total of [15, 16]	3	add 4, add 8, add 15
4	4	total of [16]	4	add 4, add 8, add 15, add 16
5	5	total of [] answers 0	5	the deepest point, five held
6	6	the 16 call finishes with 16	4	three additions still pending
7	7	the 15 call finishes with 31	3	two additions still pending
8	8	the first call finishes with 43	0	nothing held

8 steps

The pile grows all the way down and then unwinds, and every one of those additions happens on the way back up rather than on the way down. A reader who thinks of the method as adding numbers one at a time from the left has the direction exactly backwards.

Depth rather than total work

The quantity that matters here is not how many calls are made in total. It is

how many are outstanding at the same moment, which is the depth.

The distinction is sharp and it is easy to get the wrong one. A method that

walks a balanced tree of a million items makes a million calls and never holds

more than about twenty, because it finishes each branch before starting the

next. A method that counts down from a million makes a million calls and holds

all million at the deepest point, because none of them can finish until the

innermost one does.

FIG 2The memory held by a recursion

: the greatest number of calls outstanding at any one moment
: the space one unfinished call needs for its local values and its return place

The size of one held call is usually tens to a few hundred bytes, depending on how many local values the method has. The useful consequence is that cutting the depth matters and cutting the total number of calls does not, at least for memory.

FIG 3Calls made against calls held

	calls made	greatest depth	memory is a problem
walk a balanced tree of	1000000	20	0
count down from a millio	1000000	1000000	1
halve a million down to	20	20	0
walk a list of a million	1000000	1000000	1

The first and second rows make exactly the same number of calls and differ by a factor of fifty thousand in what they hold. The marked cells are the ones that fail in practice. Nothing about how these methods are written on the page makes the difference visible, which is the point of the lesson.

Why it fails rather than slows

Running out of memory usually means the program gets slower and then stops.

Running out of room for waiting calls means something sharper: the program

fails immediately, with an error about nesting.

The reason is that the space for unfinished calls is a separate region, fixed

in size when the program starts, typically a few megabytes. It is deliberately

not the region that grows. Keeping it fixed and small makes entering and

leaving a call extremely cheap, which matters because that happens constantly,

and it also means a runaway recursion is caught in milliseconds rather than

consuming the whole machine.

Some languages add their own limit well below the real one. Python stops at

around a thousand nested calls by default and reports it as an error, which is

far below the point at which the actual region would be exhausted. The limit

is there so the failure is a clean, catchable error rather than a crash with

no explanation.

Raising that limit is the first thing most people try, and it is usually the

wrong move. It converts a clear error at a thousand into an unclear one at

whatever the new number is, and if the real cause was a missing stop, it just

takes longer to arrive. The limit is worth raising only when the depth is known

to be bounded and is genuinely larger than the default, which is rare.

The lesson stops here

2 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents