Programuoki Programuoki
Theme
Code

How deep — and what happens at the end

Wire walk and depth into main.go. algo depth builds a chain — a folder inside a folder inside a folder, no branching — so the recursion depth equals n.

Guess before you read on

A Go goroutine stack grows by itself: it starts at about 8 kilobytes and expands as needed. A C thread stack is fixed — usually 1–8 megabytes — and when you reach the end, your process dies.

How deep do you think Go's recursion goes? Write the number down before you look.

The answer

$ algo depth -n 1000000
recursive walk of a chain 1000000 deep: 1000000 items, 1000001 folders, 72ms

$ algo depth -n 8000000
recursive walk of a chain 8000000 deep: 8000000 items, 8000001 folders, 621ms

Eight million frames. No trouble at all, in 0.6 seconds.

If you guessed thousands or tens of thousands — that would have been C. Go grows the stack as far as it needs, up to a default ceiling of one gigabyte.

And where it does end

$ algo depth -n 16000000
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

main.WalkRecursive(0x0?, 0x2bd4e9b5fe28)
	.../walk.go:28 +0x45 fp=0x2bd4c9b61f98 sp=0x2bd4c9b61f58
main.WalkRecursive(0x0?, 0x2bd4e9b5fe28)
	.../walk.go:28 +0x45 fp=0x2bd4c9b61fd8 sp=0x2bd4c9b61f98
...8388426 frames elided...

Three things in that message are worth your attention.

"fatal error", not "panic". You cannot catch this with recover. The program is over. It is the one Go failure you do not get to handle.

The limit is stated exactly: 1,000,000,000 bytes.

Go tells you how many frames it hid: ...8388426 frames elided.... From that you can work out the frame size:

1,000,000,000 B ÷ 8,388,426 frames ≈ 119 bytes per frame

Every WalkRecursive call costs about 119 bytes. That is the price of the "hidden" stack.

The same work, on your stack

$ algo depth -n 16000000 -iterative
iterative walk of a chain 16000000 deep: 16000000 items, 16000001 folders, 129ms

The same depth that killed the recursion. The iterative version walks it in 129 milliseconds without breaking a sweat — because its stack is a []*Folder on the ordinary heap, and the heap has no 1 GB ceiling.

And it is faster everywhere, not just at the limit: 72 ms against 8 ms at a million. A function call is not free.

Gotcha

This is exactly why transit writes BFS iteratively. Not because a 1,531-stop graph is too deep — it is not. But because recursion depth is set by the input, and a limit you cannot catch is a limit you cannot manage. When the data decides the depth, the stack has to be yours.