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, 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.)
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, 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.
Nice post, I like the benchmarking and property testing. I had a somewhat similar post: https://azdavis.net/posts/unrecur/