alt Hacker NewsIt depends on whether the limited call stack capacity will be an issue for the particular problem you’re solving.
I’m presently working on a problem which uses traversal of TypeScript file syntax trees.
I can reasonably assume that we will never get a file with a deep enough syntax tree which would cause a stack overflow.
A manually managed stack might seem safer, but as pointed out by this article the code would be more complicated and, in my case, for no good reason.
Replies
In practice, a heap-based manual stack can be as unsafe with unbounded input as using the native call stack (considering typical OOM behavior). If you have untrusted input, you might want to limit the stack depth in either case. And it’s not difficult to add a recursion counter to recursive calls. So I don’t think it’s an inherently distinguishing feature between the two approaches.
Personally I tend to find the iterative approach easier to follow when no actual stack is needed, i.e. in the tail-call case.
> I can reasonably assume that we will never get a file with a deep enough syntax tree which would cause a stack overflow.
What if eve constructs a file specifically so that you get stack overflow?
> It depends on whether the limited call stack capacity will be an issue for the particular problem you’re solving.
First: that common programming languages use the limited call stack for implementing recursion is an artifact of the programming language (implementation). One can, for example, use a stack data structure for implementing DFS instead of using the call stack; it would be no problem for a programming language implementation to use a similar method for implementing recursion.
This said: there actually exist two kinds of recursion (barely every computer science textbooks at most barely mentions this):
1. "normal" recursion (with all its problems such as potential stack overflow etc.)
2. tail recursion with guaranteed tail-call elimination (TCE) in the programming language semantics; then recursion basically behaves "like loops".
I want to clarify that it is a common exercise to convert a program that uses "normal" recursion to one that uses tail-recursion, just like it is a common exercise to convert such a program to one that uses imperative style.