Lesson 4 ended on a note: transit writes its search iteratively, with an explicit queue, not with recursion. This lesson is why.

Recursion does not remove the stack

A library with folders inside folders — a naturally recursive structure:

  root
   ├── rock
   │    ├── nineties
   │    └── classics
   └── jazz
        └── bebop

To count every item you have to descend into each folder and come back to where you were. Something has to remember where back is.

In recursion that something is the call stack — the same structure you built last lesson, except the runtime manages it instead of you. Every call to WalkRecursive lays a frame on it: arguments, local variables, and the address to return to.

Recursion does not eliminate the stack. It hides it — and hands control of it to somebody else.

In this lesson you write the same traversal twice: recursively, and iteratively with your own stack. The results will be identical, because it is the same algorithm.

Why that matters

If the stack is yours, you can see it: ask how deep it is, set a limit on it, save it and resume later.

If the stack is hidden, you can do none of that. And when it runs out, your program does not return an error — it dies.

Step 3 shows exactly how.