I would highly recommend that the author look into continuation-passing-style - the general construction they discover in their blog just seems to be a reinvention of the pretty old observation that we can make any program tail-call recursive if we write it in a CPS form. In fact, in languages like OCaml, it's fairly common to do this transformation to avoid stack overflow (typically paired with a Monad), especially when compiling to JS. The requirement of generators isn't actually needed - you just need first class functions - although, generators and coroutines do allow expressing the code in a slightly more concise way.
I'm sort of hesitant to be "that guy", but I've seen this kind of thing be a bit of a trap before. The technique of simulating a stack on the heap is useful in some situations, but it's very misleading to call it a form of safety. It's important to be clear about exactly what this buys you, and what it doesn't buy you.<p>The benefit in a case like this is that you use memory a little more efficiently (since your stack frames contain exactly what you put in them) and you have a larger maximum size (since the heap tends to have more addressable space than the stack). This buys you more recursive depth (and therefore a larger input) before crashing. You can still run out of memory and crash. Arguably on systems like 64-bit Linux this is more dangerous, since the OOM killer is less predictable than stack overflow handling.<p>Of course it is often worth it to be able to handle the input you happen to have on hand, but that's a functional improvement, not a safety improvement. It's no substitute for an algorithm that just uses less memory.
Yes, this is a standard technique. It's more or less recovering the trampoline monad via continuations as a universal monad. You can use the same technique to implement other effects as well, if you're working in the kind of crazy language that has continuations but no monads.
This seems like a universal-ish mechanism for queueing your recursive function's calls onto a dynamically resizeable stack (placed in the process's heap). This is pretty cool, but I wouldn't say it's "for free", performance-wise, as demonstrated by the performance figures in the article. Although it certainly makes the transformation cheap, implementation-wise.
> I demonstrate how to (ab)use generators/coroutines to transform any recursive function into an iterative function with nearly zero code changes.<p>That's not abuse. Reversing consumer/producer calling protocols (i.e. reversing caller/callee relationship) is exactly the fundamental purpose of generators and coroutines. It's a useful insight, nonetheless, for those exploring the fundamental problem and solution space regarding concurrency and, more generally, the reification of execution flow.
This seems like such an obvious abstraction, that it's hard to believe noone came up with a macro to do this a long time ago.<p>However, that seems like a sign of a good or well explained idea.<p>While, I've never seen something similar being used before, I wouldn't call it revolutionary since it's not really making the function iterative, it's just moving the call stack to the heap.<p>It would still be a very nice convenience for functions that are more elegantly expressed recursively.
Kotlin were the first to introduce the idea in my knowledge
<a href="https://elizarov.medium.com/deep-recursion-with-coroutines-7c53e15993e3" rel="nofollow">https://elizarov.medium.com/deep-recursion-with-coroutines-7...</a>
I would like to have the option to just mark some functions to run on the heap instead of the stack. Without that option, recursive functions are really useless and cannot be used in the real world.