[DonHopkins]

>Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation. And any tail recursive program can be transformed into a loop (a trampoline). It's really not the language construct that is the issue here.

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();
      }
  }

And you can even bind the depth for explicit depth monitoring and control:

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

[lmm]

> Not every recursion can be transformed into tail recursion. If it's not simply tail recursion [...] you still have to manage the state somewhere. There ain't no such thing as a free lunch.

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.

[AnimalMuppet]

No, still false. Anything that recurses more than once cannot. A Fibonacci series, done by recursion, cannot be done by tail recursion (without memoization). A binary tree walker that visits all the notes (as opposed to searching for one node) cannot be done with tail recursion. And so on.

[ndriscoll]

Without busting out CPS, you can also pass the current state along as parameters to your recursive calls:

    def fib(n, acc1 = 0, acc2 = 1) =
      n match
        case 0 => 0
        case 1 => acc2
        case _ => fib(n-1, acc2, acc1+acc2)

You should be able to take my tree walker here[0], add a `visit: A => ()` parameter, and call `visit(tree.value)` (assuming you have a structure Tree[A] = (value: A, children: List[Tree[A]])) before the match.

[0] https://news.ycombinator.com/item?id=43365880

[noelwelsh]

https://en.wikipedia.org/wiki/Continuation-passing_style

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

[DonHopkins]

And creating continuations for recursion requires memory allocation. How recursive! You can't just recursively move the memory allocation problem around and call it solved or somebody else's problem.

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

[noelwelsh]

I agree that algorithms that run in bounded stack space can still consume arbitrary amounts of memory, and that is the central flaw in the article that I'm responding to.

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.

[DonHopkins]

You're still implementing recursion if you implement it by hand instead of letting the compiler implement it (and it's the compiler's optimizer and code generator, not the parser, that is implementing the recursion -- the parser has nothing to do with this discussion).

The whole point of the article is about the dangers of unbounded recursion, because of its resulting unbounded memory allocation, no matter at what level or by whom that recursion is implemented.

Yes, the unbounded memory allocation is the fault of recursion, even if you're implementing the recursion yourself with dynamic memory allocations, via malloc, std::vector, dynamically allocating continuations to pass with CONS, or whatever. It's still recursion, and still unbounded dynamic memory allocation, and still dangerous.

If the ALGORITHM requires recursion that can't be optimized away as tail recursion, then it requires memory allocation. You HAVE to store the state SOMEWHERE. You can't take the recursion and unbounded memory allocation requirement out of the algorithm by using a different language, compiler, or writing it in assembly language. It's still a recursive ALGORITHM no matter how you or the compiler chose to implement it.

It's so ironic that I have to explain this so many times, because you keep recursing every time and trying to blame the problem on something else other than recursion, when it's coming from the ALGORITHM not the IMPLEMENTATION or the programmer's ability, and it's an essential part of that algorithm.

You're just playing a recursive game of whack-a-mole trying to erroneously shift responsibility away from recursion onto something else, or writing checks from one bank account and depositing them in another bank account to pay the credit card bill you used to fill another bank account you wrote checks on to pay yet another credit card bill, just to defer having to pay your first credit card bill. And you can't shoot somebody and get away with it by declaring "people don't kill people, guns kill people". Recursion kills -- the title of the article!

Yes I know you can keep recursing infinitely trying to blame something else each time than recursion, but the only time you're going to bottom out and stop recursing is when you realize that recursive algorithms that can't be simplified to tail call recursion always require memory allocation, and unless you explicitly bound them with some limit, they require unbounded memory allocation, because there is STILL no such thing as a free lunch, and continuations are not magic unicorns.

Continuation passing is NOT some magic bullet that can automatically optimize any program so it doesn't need to allocate memory for non-tail recursion. You STILL have to allocate the continuations, they don't come from nowhere, they consume memory too. So triumphantly bringing it up as if it solves the problem or indemnifies recursion from blame is a non sequitur.

It's no comfort to the user that the program they're running exploded because the programmer chose to use malloc or explicit continuation passing, instead of the built-in compiler support for recursion. Recursion is still to blame, and it comes from the ALGORITHM not the IMPLEMENTATION.

[lmm]

> And creating continuations for recursion requires memory allocation.

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