> This solution looks extremely similar to the previous one, which is a good thing. Our requirements have experienced a small change (reversing the traversal order) and our solution has responded with a small modification.
Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes. You can make either approach look natural and elegant if you pick the right example.
> Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes.
The reason is that no programming language that is in widespread use has first-class support for co-recursion. In a (fictional) programming language that has this support, this is just a change from a recursive call to a co-recursive call.
def visit_bf(g):
n, children = g
yield n
if children:
iterators = [iter(visit_df(c)) for c in children]
while iterators:
try:
yield next(iterators[0])
except StopIteration:
iterators.pop(0)
iterators = iterators[1:] + iterators[:1]
The difference between DFS and BFS is literally just the last line that rotates the list of child trees.
Python is a pretty mainstream language and even though the DFS case can be simplified by using yield from and BFS cannot, I consider that just to be syntactic sugar on top of this base implementation.
>
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.
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.
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.
This page is a good example of when Typescript is both unnecessary and off-putting, based on the content's purpose.
The author is trying to demonstrate a problem and the proposed solution, using example code that the reader then needs to read, formulate a visual "structure" in their mind, and then apply that structure to the subsequent code.
Typescript is not in any way invalid here, and as a tool when programming something that will run in the real-world, can be invaluable.
However, when writing anything you want someone to deeply comprehend, you want to use the least amount of text needed to get your point across. Adding types don't serve any purpose here. The types used are generics, which tell you nothing specific, hence the name, and the names given to the functions and object properties are enough to convey what this code is doing.
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?
> It seems to be common knowledge that any recursive function can be transformed into an iterative function.
Huh. Where i work, the main problem is that everyone is hell-bent on transforming every iterative function into a recursive function. If i had a pound for every recursive function called "loop" in the codebase, i could retire.
PL-specific problem, but: the Rust borrow checker tends to give you a lot of trouble when writing iterative algorithms on nonlinear data structures, because it has trouble reasoning about partial borrows.
The upcoming Polonius borrow checker is supposed to solve this, but it's still in alpha...
28 comments
> This solution looks extremely similar to the previous one, which is a good thing. Our requirements have experienced a small change (reversing the traversal order) and our solution has responded with a small modification.
Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes. You can make either approach look natural and elegant if you pick the right example.
> Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes.
The reason is that no programming language that is in widespread use has first-class support for co-recursion. In a (fictional) programming language that has this support, this is just a change from a recursive call to a co-recursive call.
Python is a pretty mainstream language and even though the DFS case can be simplified by using
yield fromand BFS cannot, I consider that just to be syntactic sugar on top of this base implementation.Thanks!
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.
> 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.
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.
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?
The author is trying to demonstrate a problem and the proposed solution, using example code that the reader then needs to read, formulate a visual "structure" in their mind, and then apply that structure to the subsequent code.
Typescript is not in any way invalid here, and as a tool when programming something that will run in the real-world, can be invaluable.
However, when writing anything you want someone to deeply comprehend, you want to use the least amount of text needed to get your point across. Adding types don't serve any purpose here. The types used are generics, which tell you nothing specific, hence the name, and the names given to the functions and object properties are enough to convey what this code is doing.
> It seems to be common knowledge that any recursive function can be transformed into an iterative function.
Huh. Where i work, the main problem is that everyone is hell-bent on transforming every iterative function into a recursive function. If i had a pound for every recursive function called "loop" in the codebase, i could retire.
The upcoming Polonius borrow checker is supposed to solve this, but it's still in alpha...