Recursive Problems Benefit from Recursive Solutions (opens in new tab)

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

No need for radical changes.

  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.

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

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

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.

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

My experience has gone the other way: lots of code with recursion, rewritten to be iterative. There really aren't that many use-cases in vanilla enterprise code that benefit from recursion when the entire cost is considered.

Where on earth do you work? This is unusual...