One reason I've found in practice to use iteration even in cases when recursion makes lots of sense (e.g., divide-and-conquer algorithms): the ability to periodically save the state of the computation to disk, and resume it later. Every time I write a big recursive routine and set it running for days, I end up cursing my lack of foresight for not implementing checkpoints. (Of course, there's the brute-force workaround of using CRIU, but it is extremely painful to get all the file descriptors set up just right on restore.)
Given that turning an active call stack into a serializable form is such a rare feature even in functional languages, iteration with an explicit stack ends up as the only practical choice for this use case.
(Also, for this particular problem, we can implement a much simpler iterative routine: create an explicit stack of forests, initially containing the initial forest. While the stack is not empty, pop a forest: if it is not nil, push its tail, then if its head tree is not empty, then accumulate the value and push the sub-forest. If you're starting with a tree, then stick it in a synthetic forest. This all comes out to ~15 LOC, with no mutability except for the accumulator and stack.)
Is the idea that this is for situations you can't set `ulimit -s` ?
This seems like a lot of work when you could just increase the stack size instead.
One reason I've found in practice to use iteration even in cases when recursion makes lots of sense (e.g., divide-and-conquer algorithms): the ability to periodically save the state of the computation to disk, and resume it later. Every time I write a big recursive routine and set it running for days, I end up cursing my lack of foresight for not implementing checkpoints. (Of course, there's the brute-force workaround of using CRIU, but it is extremely painful to get all the file descriptors set up just right on restore.)
Given that turning an active call stack into a serializable form is such a rare feature even in functional languages, iteration with an explicit stack ends up as the only practical choice for this use case.
(Also, for this particular problem, we can implement a much simpler iterative routine: create an explicit stack of forests, initially containing the initial forest. While the stack is not empty, pop a forest: if it is not nil, push its tail, then if its head tree is not empty, then accumulate the value and push the sub-forest. If you're starting with a tree, then stick it in a synthetic forest. This all comes out to ~15 LOC, with no mutability except for the accumulator and stack.)
Nice post, I like the benchmarking and property testing. I had a somewhat similar post: https://azdavis.net/posts/unrecur/