Mastodon-->

Revealing the frontier with stacks and queues

Table of Contents

Introduction

Tree traversal

Depth-first traversal in natural order

When no order is required

Breadth-First Search

Graph exploration

The core approach

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.<br>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(<br>dir: &Path,<br>list: &mut Vec,<br>max: usize,<br>) -> Result {<br>if list.len() >= max { return Ok(()); }<br>list.push(dir.to_path_buf());<br>if dir.is_dir() {<br>for entry in fs::read_dir(dir)? {<br>let path = entry?.path();<br>add_first_paths_recursive(&path, list, max)?;<br>if list.len() >= max { break; }<br>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(<br>dir: &Path,<br>list: &mut Vec,<br>max: usize,<br>) -> Result {<br>let mut todo = vec![dir.to_path_buf()];<br>while let Some(current) = todo.pop() {<br>if list.len() >= max { break; }<br>if current.is_dir() {<br>let mut children = Vec::new();<br>for entry in fs::read_dir(&current)? {<br>let path = entry?.path();<br>children.push(path);<br>list.push(current);<br>for path in children.into_iter().rev() {<br>todo.push(path);<br>} else {<br>list.push(current);<br>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(<br>dir: &Path,<br>list: &mut Vec,<br>max: usize,<br>) -> Result {<br>let mut todo = vec![dir.to_path_buf()];<br>while let Some(current) = todo.pop() {<br>if list.len() >= max { break; }<br>if current.is_dir() {<br>for entry in fs::read_dir(&current)? {<br>let path = entry?.path();<br>todo.push(path);<br>list.push(current);<br>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.

Breadth-First Search

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(<br>dir: &Path,<br>list: &mut Vec,<br>max: usize,<br>) -> Result {<br>let mut todo = VecDeque::from([dir.to_path_buf()]);<br>while let Some(current) = todo.pop_front() {<br>if list.len() >= max { break; }<br>if current.is_dir() {<br>for entry in fs::read_dir(&current)? {<br>let path = entry?.path();<br>todo.push_back(path);<br>list.push(current);<br>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...