Table of Contents

Being able to think in stacks and queues is a neglected super-power.

It's often a better way to see problems than recursion when trees and other graphs are involved.

CS Courses like to teach recursion, because it looks simple and elegant, especially when Functional Programming is in the curriculum, and especially when drawn on a black board.

You've probably already read a few times, and maybe experienced yourself, that recursion isn't always efficient, especially on modern computers.

But a more interesting point is that it's also often a poor mental model which makes programming more complex and less adaptable.

An even more interesting point is that sometimes recursion shines, and that's why it didn't go away.

But even that isn't the real point of this article.

Tree traversal

Let's start our exploration with the case of file tree traversal.

In the real world, you never list all deep files in a directory: you have to deal with user interruptions, timeouts, various limits. We'll keep it simple and simulate this complexity with just a maximum number of items.

Depth-first traversal in natural order

In Rust the recursive code could look like this:

fn add_first_paths_recursive(
    dir: &Path,
    list: &mut Vec<PathBuf>,
    max: usize,
) -> Result<(), io::Error> {
    if list.len() >= max { return Ok(()); }
    list.push(dir.to_path_buf());
    if dir.is_dir() {
        for entry in fs::read_dir(dir)? {
            let path = entry?.path();
            add_first_paths_recursive(&path, list, max)?;
            if list.len() >= max { break; }
        }
    }
    Ok(())
}

What this does, is it lists files as they would appear with a standard tree representation, Depth-First Search, and files listed in the same order as returned by the system.

The code is obvious, you know there won't be any surprise, the order will be as expected. There's of course the hidden cost of the stack allocation but it's minor.

Early exit behaviour is a little more painful, both in code (hard not to repeat it) and in execution (as the call stack is unwound, every step has to do the same test).

Now, let's have a look at a stack based function doing the same traversal in the same order. It's less pretty than expected:

fn add_first_paths_with_stack_dfs(
    dir: &Path,
    list: &mut Vec<PathBuf>,
    max: usize,
) -> Result<(), io::Error> {
    let mut todo = vec![dir.to_path_buf()];
    while let Some(current) = todo.pop() {
        if list.len() >= max { break; }
        if current.is_dir() {
            let mut children = Vec::new();
            for entry in fs::read_dir(&current)? {
                let path = entry?.path();
                children.push(path);
            }
            list.push(current);
            for path in children.into_iter().rev() {
                todo.push(path);
            }
        } else {
            list.push(current);
        }
    }
    Ok(())
}

As we add paths to a TODO list that we unstack, we need to iterate in reverse (hence the children.into_iter().rev()).

This makes the code much harder to decipher (and even to write right at first try).

Early exit is much better handled but let's be honest, this code is much less obvious.

Here recursion shines.

It may be a little less efficient when handling the constraints of real world applications, like interrupts, but in this case, the recursive code perfectly aligns with our intent.

When no order is required

If we're not trying to print a tree on the fly, recursion isn't the simplest solution.

This one is very simple with a stack acting as a TODO list of directories to visit:

fn add_first_paths_with_stack(
    dir: &Path,
    list: &mut Vec<PathBuf>,
    max: usize,
) -> Result<(), io::Error> {
    let mut todo = vec![dir.to_path_buf()];
    while let Some(current) = todo.pop() {
        if list.len() >= max { break; }
        if current.is_dir() {
            for entry in fs::read_dir(&current)? {
                let path = entry?.path();
                todo.push(path);
            }
        }
        list.push(current);
    }
    Ok(())
}

Nothing awkward in this one.

And because we reified the frontier, it's very easy to change the control flow, to deal with interrupts, pause the iteration, have interleaving tasks, like iterating on another tree at the same time, etc.

What if you want to fully explore the current level before moving deeper ?

This is a trivial change: just replace the LIFO stack with a FIFO queue (using a VecDeque in Rust):

fn add_first_paths_with_queue(
    dir: &Path,
    list: &mut Vec<PathBuf>,
    max: usize,
) -> Result<(), io::Error> {
    let mut todo = VecDeque::from([dir.to_path_buf()]);
    while let Some(current) = todo.pop_front() {
        if list.len() >= max { break; }
        if current.is_dir() {
            for entry in fs::read_dir(&current)? {
                let path = entry?.path();
                todo.push_back(path);
            }
        }
        list.push(current);
    }
    Ok(())
}

The control flow is still easy to handle and the logic can be tuned.

For example broot builds upon this to provide efficient search and parallel descent without locking the UI.

Graph exploration

When the graph is more connected than a tree, exploring it with pure recursion becomes impossible.

But the stack/queue approach stays simple.

For example, here's returning all the nodes that can be reached from one:

fn reachable_from(root: Node) -> HashSet<Node> {
    let mut visited = HashSet::new();
    let mut todo = VecDeque::new();
    visited.insert(root);
    todo.push_back(root);
    while let Some(current) = todo.pop_front() {
        for neighbour in neighbours_of(current) {
            if visited.insert(neighbour) { // Returns false if already present
                todo.push_back(neighbour);
            }
        }
    }
    visited
}

This is very easy to tune:

  • Use a Vec for todo instead of the VecDeque and you explore far nodes first (equivalent of DFS)
  • Don't return visited but just the first node verifying a constraint and you check whether you can reach a set

You get pathfinding with just a small addition: store for each node the node they come from:

fn find_path(from: Node, to: Node) -> Option<Vec<Node>> {
    let mut todo = VecDeque::from([from]);
    // Act as both the 'visited' set and the history tracker
    let mut came_from: HashMap<Node, Node> = HashMap::new();

    while let Some(current) = todo.pop_front() {
        if current == to {
            // Reconstruct the path at the very end
            let mut path = vec![current];
            while let Some(&parent) = came_from.get(path.last().unwrap()) {
                path.push(parent);
            }
            path.reverse();
            return Some(path);
        }

        for neighbour in neighbours_of(current) {
            if neighbour != from && !came_from.contains_key(&neighbour) {
                came_from.insert(neighbour, current);
                todo.push_back(neighbour);
            }
        }
    }
    None
}

Replace the queue with a binary heap to first search the nodes estimated closest to your target and you have A*.

Notice how it's still a linear operation, how you could add tests, pause, or even store the search state ?

The core approach

The core of the approach isn't just stacks, and queues, and binary heaps, it's the reification of the frontier, converting temporal execution into just data, making it manageable, pausable, and easier to reason with.

With some habit of thinking this way, a whole world of problems becomes easy to solve, not with CS algorithms you're copying from a book but naturally and with all the constraints of real world problems.

I only mentioned graphs here, but you encounter the exact same architectural stakes with recursive descent parsers, regular expression engines (which can be re-engineered into explicit automata), or game behavior trees. Whenever you turn execution flow into data, your system becomes inherently controllable, testable, and actionable.