5 ms·

>Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation. And any tail recursive program can be tr

>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 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 2y ago
> 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 2y ago
  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.
  - noelwelsh 2y ago
    https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style "Programs can be automatically transformed ... to CPS. ... Every call in CPS is a tail call"
    - DonHopkins 2y ago
      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 2y ago
        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.

lmm 2y ago

> 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 2y ago
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.
- noelwelsh 2y ago
  https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style "Programs can be automatically transformed ... to CPS. ... Every call in CPS is a tail call"
  - DonHopkins 2y ago
    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 2y ago
      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.