Removing recursion via explicit callstack simulation(jnkr.tech)

Removing recursion via explicit callstack simulation

https://jnkr.tech/blog/removing-recursion

5 コメント

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.)

[deleted]4 か月前

azdavis4 か月前

Nice post, I like the benchmarking and property testing. I had a somewhat similar post: https://azdavis.net/posts/unrecur/

bawolff4 か月前

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.

WalterGR4 か月前

How 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?