[swiftcoder]

This has always felt like the kind of thing we could be building compilers to solve. Recursive -> explicit stack is a very mechanical conversion, why can't we write a compiler transform pass that does that rewrite any time it detects a high potential for stack overflow?

[derriz]

It’s called TCO - tail call optimization - and gcc and llvm are supposed to implement it although tail recursive style code is probably uncommon in C or C++. Outside of that it’s common in functional languages where recursive functions are obviously idiomatic and so it has more potential to provide performance benefit.

It’s not a purely local optimization - affecting the call structure so debugging is a pain point. Which is probably why most imperative language compilers don’t bother given the lack of utility for the vast majority of code bases.

It feels like something that would need to be specified at the language spec or semantics level to make it useful rather than just making it optional for the compiler - otherwise the developer is probably just going to do the transform manually - to be safe - if stack explosion was a possibility if the compiler decided on a whim to not perform TCO.

[ufo]

Tail call optimization optimizes the situations where the recursion doesn't actually need any stack space, but I think the parent poster is asking about situations that aren't tail recirsive.

[afiori]

Just like many languages have annotations for inlining functions they could have annotations for tco. From an usability pov i would like annotations for must, must not, should, and should not. Where the "must" versions error if the compiler can't do the optimization

[a57721]

Scala and Kotlin have 'tailrec' annotation/modifier, though not as sophisticated as you describe.

[Epa095]

Yeah, tail call elimination, is definitely doable.

Python famously does not have it because "Language inventor Guido van Rossum contended that stack traces are altered by tail-call elimination making debugging harder, and preferred that programmers use explicit iteration instead". https://en.wikipedia.org/wiki/Tail_call

[ufo]

It's indeed very mechanical and some programming languages can do it for you.

I think you're mainly asking for heap-allocated stacks. Some languages always use the heap for stack frames instead of the native stack and can set the stack limit as high as there's memory available.

You might also want to look into stackful coroutines, which allow one to pause the execution of a recursive function and switch to another function. This can provide you with multiple call stacks, which is another reason people sometimes choose to use write explicit stacks.

[Jaxan]

Many compilers do change a recursion into a loop, avoiding the stack altogether!