Removing recursion via explicit callstack simulation
4 days ago
- #recursion
- #stack-safety
- #typescript
- Recursive implementations are often the most maintainable way to solve inherently-recursive problems.
- The post discusses a technique for converting recursive code into an imperative form to avoid stack overflow in languages like TypeScript and node.js.
- The technique involves simulating the call stack manually by representing stack frames as first-class values.
- Examples are provided using linked lists and binary trees to illustrate the conversion from recursive to iterative forms.
- The iterative solution for summing a linked list avoids stack overflow by using a pointer to traverse the list iteratively.
- For binary trees, the iterative solution uses a stack to manage the traversal manually, simulating the call stack.
- The post introduces a more complex example involving mutually recursive tree and forest types to demonstrate the technique's applicability to challenging scenarios.
- A detailed walkthrough of converting a recursive fold function for trees and forests into an iterative form is provided.
- Property-based testing is used to verify the correctness of the iterative implementation against the recursive reference.
- Performance benchmarks show that the iterative solution is about 2.2x slower than the recursive one, which is considered acceptable given the trade-offs.
- Limitations of the technique are discussed, particularly its inability to handle polymorphically recursive functions directly.
- The post concludes with open questions about alternative approaches and references to related work.