[jonathanlydall]

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

[aleph_minus_one]

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

[jonathanlydall]

Yes, languages and/or engines with this feature can eliminate any concerns about stack overflows.

But in this particular case I'm using JavaScript (since at this time it has the best libraries for working with TypeScript ASTs) running under Node.js, and my understanding is that is has no tail call optimization.

The other language I mostly work in is C#, which also similarly lacks it.

So, at this time in the languages I work in, I need to consider possible stack overflows whenever I use recursion.

[layer8]

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.

[randomNumber7]

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

[jonathanlydall]

Eve will then experience a stack overflow exception on our app running on her PC, no doubt she will be very impressed with her achievement.

[randomNumber7]

Ok, but then your argumentation is only valid for programming languages with build in saftey guards. In low level languages this would be a recipe for disaster.