3 ms·
Removing recursion via explicit callstack simulation
- azdavis 7mo agoNice post, I like the benchmarking and property testing. I had a somewhat similar post: https://azdavis.net/posts/unrecur/ https://azdavis.net/posts/unrecur/
- deleted 7mo ago[deleted]
- LegionMammal978 7mo agoOne 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.)
- bawolff 7mo agoIs 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.
- WalterGR 7mo agoHow well does that work on code running in an interpreter? Which interpreters have a 1:1 mapping between language-being-interpreted stack frames and native stack frames?