Elegant and performant recursion in Rust


Source URL:: https://recursion.wtf/posts/rust_schemes/
Topics:: #rust, #recursion, #perf

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.