code

In traditional low level languages such as C iteration is implemented manually, with users writing out for (int idx = 0; idx < items_len; ++idx) { do_thing(items[idx] } , every time they want to iterate over a list. Newer languages like Rust provide abstractions - iterators - that separate the machinery of recursion from the logic: for item in items.iter() { do_thing(item) } .

The recursion crate does the same thing for recursive data structures. This post is an introduction to the new version of the recursion crate, but you don’t have to read my earlier posts to understand it.

This is the third post in a three-post series. In the first post we developed a stack-safe, ergonomic, and concise method for working with recursive data structures (using a simple expression language as an example). In the second post we made it fully generic, providing a set of generic tools for expanding and collapsing any recursive data structure in Rust.

In this post we will see how to combine these two things - expanding a structure and collapsing it at the same time, performing both operations in a single pass. In the process, we will gain the ability to write arbitrary recursive functions over traditional boxed-pointer recursive structures (instead of the novel RecursiveTree type introduced in my previous post) while retaining stack safety.

Previously, we introduced a method for writing performant stack safe recursion in Rust for a single recursive data structure. This post uses the same ideas to implement a single recursion backend that can collapse or expand any recursive data structure.

This is a post about writing elegant and performant recursive algorithms in Rust. It makes heavy use of a pattern from Haskell called recursion schemes, but you don’t need to know anything about that; it’s just an implementation detail. Instead, as motivation, I have benchmarks showing a 14-34% improvement over the typical boxed pointer representation of recursive data structures in Rust.