You know, I got spoiled by Haskell, doing recursion everywhere without a care, and all I had to think was the evaluation order (when things blew up). Now that I'm doing some OCaml, I have to stop and think "am I writing a tail recursive function". It's easy to write multiple levels of recursion and lose track if you're writing a tail recursive function that the compiler will optimize.

I think recursions are really easy to make unbounded by mistake. Maybe not so much as for loops and off by ones.

However I don't think that is the case in Expat. If the algorithm is tail recursive, but accidentally not expressed in that way, its a simple (but perhaps tedious to manually apply) program transform to express it in a way that does not consume unbounded memory (heap or stack). From the scant details on the fix in the article it appears the parsing algorithm itself was completely changed. ("The third variant "Parameter entities" reuses ... the same mechanism of delayed interpretation.") If this is the case the issue is not recursion, as the original parsing algorithm would consume unbounded resources no matter how it was expressed in C.

A computer can chug through millions of loop iterations. I don't think tail recursion will ever result in heap exhaustion. But a stack overflow can be caused with tens of thousands of nested calls, which is tiny in comparison.

Recursion based stack overflow issues are easier to exploit because modern computer's stack space is much smaller relative to other resources.

Sounds like a design issue in particular language implementations rather than a problem with the programming technique.

You say this like these are fundamentally separable things? I find this comment deeply confusing. Every single real software stack ever has a layer where the sausage gets made so to speak.

What is the outdated programming practice at fault here?

For this particular CVE? I'm not clear. Possibly none. The writeup didn't provide sufficient detail and I haven't bothered to wade through the code. There may well be a reason recursion won't work here but it certainly isn't general.

I'd be curious to know in this case why resource limits couldn't be enforced for the recursive implementation but could be for the iterative one.

    fn recurse (tree) :
        for child in tree.children :
            recurse(child)

And it gets more complex when there's a bunch of state that requires you to save the stack frame in your explicit stack.

If the language runtime has growable stacks you're just making the code more complex.

You are incorrect about tail recursion (look at continuation-passing style; it transforms any program to tail recursive form) but you are getting at the core of the issue here. The issue is either:

* whatever the parser is doing is already tail recursive, but not expressed in C in a way that doesn't consume stack. In this case it's trivial, but perhaps tedious, to convert it to a form that doesn't use unbounded resources.

* whatever the parser is doing uses the intermediate results of the recursion, and hence is not trivially tail recursive. In this case any reformulation of the algorithm using different language constructs will continue to use unbounded resources, just heap instead of stack.

In other words, you can shift memory usage from the stack to the heap, but if a client can give you an unbounded amount of memory consuming work you are screwed either way. Ultimately the problem has nothing to do with recursion.

But you're right, that's what I'm getting at. Recursion is an inherent semantic and whether you make the stack explicit or implicit doesn't get rid of memory allocation problems. I said in another comment that stack allocation is still dynamic memory management, it's just something many people take for granted.

Not every recursion can be transformed into tail recursion. If it's not simply tail recursion (which is the high level language compiler way of implementing the old tried and true assembly language optimization technique of making the last function call be a JMP instead of a JSR followed by an RTS, that I learned from WOZ's Apple ][ 6502 monitor ROM code), you still have to manage the state somewhere. There ain't no such thing as a free lunch.

And if not on the C stack, then it has to be somewhere else, like another stack or linked list, and then you still have to apply your own limits to keep it from being unlimited, so you're back where you started (but in a Sisyphusly tail call recursive way, you still have to solve the problem again).

https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

>Greenspun's tenth rule of programming "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."

Of course you can always just pass a recursion depth limit parameter down the recursion and stop when it expires, even letting the caller decide how deep a recursion they want to permit, which is easier and safer than using malloc or cons or std::vector to roll your own stack.

Or the compiler could even do that for you, but you still have to figure out how to gracefully bottom out...

So if "Exception Handling" is hopefully failing upward, then "Depthception Handling" is hopelessly failing downward!

Depthception Handling is the vertical reflection of Exception Handling, with "implicit depth" recursion depth passing, like C++'s "implicit this" but deeper, not to be confused with the orthogonal "continuation passing" / "halt passing" dichotomy (passing HALT and CATCHFIRE instructions around but promising to never call them except in fatal emergencies):

"try" / "catch" = An active attempt to solve things.

"giveup" / "bottom" = Passive resignation to inevitability.

"throw" is an emergency exit UP.

"drop" is an emergency slide DOWN.

"try" => "giveup" introduces a futile attempt at unbounded recursion.

"catch" => "bottom" declares a bottoming out handler after a function signature, to guard its body below.

"throw" => "drop" immediately bottoms out from any depth!

  fn doomed_recursion()
  bottom { println!("Too deep, I give up."); }
  {
      giveup {
          if going_too_deep() {
              drop;
          }
          doomed_recursion();
      }
  }

  fn deep_trouble(depth: Depth)
  bottom { println!("I reached depth {} and surrendered.", depth); }
  {
      giveup depth {
          if depth > 10 {
              drop;
          }
          deep_trouble(depth++);
      }
  }

Ok, every recursion in a language that supports programmer-managed state can be transformed into a tail recursion. That still means any recursion in all serious programming languages and most joke programming languages too.

"Programs can be automatically transformed ... to CPS. ... Every call in CPS is a tail call"

At least start with a rigorous, well-specified, robust, high-performance, complete implementation of Common Lisp, if you're going to recurse infinitely.

The issue is either:

* whatever the parser is doing is already trivially tail recursive, but not expressed in C in a way that doesn't consume stack. In this case it's trivial, but perhaps tedious, to convert it to a form that doesn't use unbounded resources.

* whatever the parser is doing uses the intermediate results of the recursion, and hence is not trivially tail recursive. In this case any reformulation of the algorithm using different language constructs will continue to use unbounded resources, just heap instead of stack.

Either way it is not the fault of recursion.

Can't all recursive functions be transformed to stack-based algorithms? And then, generally, isn't there a flatter resource consumption curve for stack-based algorithms, unless the language supports tail recursion?

E.g. Python has sys.getrecursionlimit() == 1000 by default, RecursionError, collections.deque; and "Performance of the Python 3.14 tail-call interpreter": https://news.ycombinator.com/item?id=43317592

Yes, you can explicitly manage the stack. You still consume memory at the same rate, but now it is a heap-allocated stack that is programmatically controlled, instead of a stack-allocated stack that is automatically controlled.

The issue is either:

* whatever the parser is doing is already tail recursive, but not expressed in C in a way that doesn't consume stack. In this case it's trivial, but perhaps tedious, to convert it to a form that doesn't use unbounded resources.

* whatever the parser is doing uses the intermediate results of the recursion, and hence is not trivially tail recursive. In this case any reformulation of the algorithm using different language constructs will continue to use unbounded resources, just heap instead of stack.

It's not clear how the issue was fixed. The only description in the blog post is "It used the same mechanism of delayed interpretation" which suggests they didn't translate the existing algorithm to a different form, but changed the algorithm itself to a different algorithm. (It reads like they went from eager to lazy evaluation.)

Either way, it's not recursion itself that is the problem.

To be precise; with precision:

In C (and IIUC now Python, too), a stack frame is created for each function call (unless tail call optimization is applied by the compiler).

To avoid creating an unnecessary stack frame for each recursive function call, instead create a collections.deque and add traversed nodes to the beginning or end enqueued for processing in a loop within one non-recursive function.

Is Tail Call Optimization faster than collections.deque in a loop in one function scope stack frame?