7 ms·

Practically the day after I learned about tail recursion in CS class, I learned that almost all recursive calls can be translated to iteration, that in many cas

Practically the day after I learned about tail recursion in CS class, I learned that almost all recursive calls can be translated to iteration, that in many cases the iterative version is easier to scan, is as fast if not faster, and that they can usually handle much much larger inputs than recursion due to avoiding stack overflow. Tail recursion is meant to fix the latter. But what we mean to happen and what actually happens ain't ever exactly similar. Tail recursion IME is a bigger foot gun than relying on someone to add a new conditional branch at the end of a block in an iterative algorithm without fucking it up in the process. And iteration responds generally better to Extract Function. And while I can think of counter cases easily enough, in the large iteration is less work and less vigilance. And you cannot scale a project up without the vigilance requirement amortizing basically to 0 per line of code.

tombert 1y ago
In my mind, the biggest advantage to using tail recursion over vanilla loops is the ability to keep using persistent data structures without any (apparent) mutation. At least in theory, a tail recursive call will be converted into a dumb jump, so there shouldn't be a performance penalty, but since from your code's perspective you're passing in the stuff for the next iteration, you can keep using the pretty and easy-to-reason-about structures without creating any kind of mutable reference. I'm not 100% sold on tail recursion in a broader sense, but at least with Clojure's loop/recur stuff it is kind of cool to be able to keep using persistent data structures across iterations of loops.
- weitendorf 1y ago
  What makes tail recursion "special" is that there exists a semantically equivalent mutable/iterative implementation to something expressed logically as immutable/recursive. [0] Of course, this means that the same implementation could also be directly expressed logically in a way that is mutable/iterative. func pow(uint base, uint n): n == 0 ? return 1 : return n * pow(base, n-1) is just func pow(uint base, uint n): uint res = 1; for(i=0; i<n; i++){ res *= n} return res There is no real "advantage" to, or reason to "sell" anybody on tail call recursion if you are able to easily and clearly represent both implementations, IMO. It is just a compiler/runtime optimization, which might make your code more "elegant" at the cost of obfuscating how it actually runs + new footguns from the possibility that code you think should use TCO actually not (because not all immutable + recursive functions can use TCO, only certain kinds, and your runtime may not even implement TCO in all cases where it theoretically should). As an aside, in C++ there is something very similar to TCO called copy-elision/return-value-optimization (RVO): [1]. As with TCO it is IMO not something "buy into" or sell yourself on, it is just an optimization you can leverage when structuring your code in a way similar to what the article calls "continuation passing style". And just like TCO, RVO is neat but IMO slightly dangerous because it relies on implicit compiler/runtime optimizations that can be accidentally disabled or made non-applicable as code changes: if someone wanders in and makes small semantic to changes to my code relying on RVO/TCO for performance they could silently break something important. [0] EXCEPT in practice all implementation differences/optimizations introduce observable side effects that can otherwise impact program correctness or semantics. For example, a program could (perhaps implicitly) rely on the fact that it errors out due to stack overflow when recursing > X times, and so enabling TCO could cause the program to enter new/undesirable states; or a program could rely on a functin F making X floating point operations taking at least Y cycles in at least Z microseconds, and not function properly when F takes less than Z microseconds after enabling vectorization. This is Hyrum's Law [2]. [1] https://en.wikipedia.org/wiki/Copy_elision#Return_value_optimization https://en.wikipedia.org/wiki/Copy_elision#Return_value_opti... [2] https://www.hyrumslaw.com/ https://www.hyrumslaw.com/
  - gleenn 1y ago
    I would argue having the parameters that change during the loop be explicit is a very nice advantage. Agree that the things can be equivalent in terms of execution but the readability and explicitness, and the fact that all the parameters are listed in the same place is great.
    - weitendorf 1y ago
      Agreed. Some people really like FP a lot, and I think it's underrated that the kinds of functions where TCO is applicable tend to be so simple that they are not really that inelegant when expressed imperatively. My true opinion is that relying on TCO is usually choosing ideological adherence to FP (or "code that looks cooler") over reliability/performance/communication. That said, just as I'd expect experienced C++ programmers to be able to recognize others' code using RVO and be careful not to restructure things to break it, I'd concede that experienced FP programmers might be unlikely to accidentally break others' TCO. It's just that ad absurdum you cannot expect every developer to be able to read every other developers' mind and recognize/workaround all implicit behavior they encounter.
      - eru 1y ago
        > [...] and I think it's underrated that the kinds of functions where TCO is applicable tend to be so simple that they are not really that inelegant when expressed imperatively. I suspect you are only thinking of patterns that are basically equivalent to a loop. I might agree with that. TCO really shines when you want to implement state machines. See eg https://news.ycombinator.com/item?id=43076088 https://news.ycombinator.com/item?id=43076088 for an example where using tail calls in Python's interpreter loop gives nice performance benefits. Similar also for LUA. > [...] I'd concede that experienced FP programmers might be unlikely to accidentally break others' TCO. Compiler (or linter) checkable annotations would help here. You are right that you want to make it possible for programmers to statically assert somehow that their function call is a tail call. Btw this reminds me: recursion isn't just something you do in computation, but also in data structures (amongst other things). In eg Rust the members of your data structure are typically just laid out one after another, but when you have a recursive structure (and in certain other cases) you need to box it, otherwise you'd get an infinitely large data structure. Boxing is more or less equivalent to using indirection via a pointer. However, unboxing isn't really like TCO. It's more like in-lining.
- ramchip 1y ago
  I think you're confusing mutation and variable reassignment?
  - tombert 1y ago
    I'm saying that if I do a regular loop, something needs to explicitly mutate, either a reference or a value itself. `for (var i = 0; i < n, i++)`, for example, requires that `i` mutate in order to keep track of the value so that the loop can eventually terminate. You could also do something like: var i = new Obj(); while (!i.isDone()) { //do some stuff i = new Obj(); } There, the reference to `i` is being mutated. For tail recursion, it's a little different. If I did something like Factorial: function factorial(n, acc) { if (n <= 1) return acc; return factorial(n - 1, acc * n); } Doing this, there's no explicit mutation. It might be happening behind the scenes, but everything there from the code perspective is creating a new value. In something like Clojure, you might do something like (defn vrange [n] (loop [i 0 v []] (if (< i n) (recur (inc i) (conj v i)) v))) (stolen from [1]) In this case, we're creating "new" structures on every iteration of the loop, so our code is "more pure", in that there's no mutation. It might be being mutated in the implementation but not from the author's perspective. I don't think I'm confusing anything. [1] https://clojure.org/reference/transients https://clojure.org/reference/transients
    - eru 1y ago
      You could imagine a language like eg Python with a for-each loop that creates a new variable for each run through the loop body. Basically, just pretend the loop body is a lambda that you call for each run through the loop. It might make sense to think of the common loops as a special kind of combinator (like 'map' and 'filter', 'reduce' etc.) And just like you shouldn't write everything in terms of 'reduce', even though you perhaps could, you shouldn't write everything in terms of the common loops either. Make up new combinators, when you need them. For comparison, in Haskell we seldom use 'naked' recursion directly: we typically define a combinator and then use it. That often makes sense, even if you only use the combinator once.
    - ramchip 1y ago
- charcircuit 1y ago
  >without creating any kind of mutable reference. The parameter essentially becomes a mutable reference.
  - tombert 1y ago
    No disagreement on that but that's an implementation detail and from the coder's perspective there's no mutable references.
    - charcircuit 1y ago
      From the coder's perspective it is. There's just different syntax for assigning to them.
      - tombert 1y ago
        No, from the coder's perspective it looks like I'm passing an argument into a function. I suppose you could say that arguments in general are "mutable references", and I guess that's not necessarily "untrue", but that's not generally how I visualize it. If I pass a persistent structure into a tail call, it looks like I'm passing a copy into there, in the same way that I might if I did something like `Math.abs(myValue * 3)`; the compiler converts it to a mutable reference but I see it as the same as passing a value.
    - weitendorf 1y ago
      From the coder's perspective, there are no mutable references only if the coder does not really rely on or care about the possibility that their code uses TCO. If they actively want TCO then they definitely care about the performance benefits they get from underlying mutability/memory reuse/frame elision.
      - tombert 1y ago
        Yeah but that's why I prefer Clojure's loop/recur thing. You're not allowed to have non-tail recursion there, so it's not implicit, so you really can pretend that there's no mutable references.
CalChris 1y ago
I must have missed this class. How does one convert a recursive descent parser into an iterative one?
- pmg101 1y ago
  https://news.ycombinator.com/item?id=44837949 https://news.ycombinator.com/item?id=44837949
- jandrese 1y ago
  By making your own stack and using loops.
- kylec 1y ago
  You can do it by managing your own stack, but I would argue that doing so makes the algorithm LESS easy to scan and has its own sets of problems.
- electroly 1y ago
  Same way as any other algorithm: with an explicit heap-allocated stack. I have a naive parser where I built operator precedence into the grammar as nested productions instead of using an algorithm like shunting yard. An input of ((((((1)))))) blew the stack. Converted it to an explicit stack and it was fine; deep for the call stack was not deep for my own heap-allocated stack. Nasty code, though--I think this serves as one of the counterexamples to the idea that the recursive code gets simpler when turning it into iteration. The original OP was talking more specifically about tail recursion, which a recursive descent parser won't be.
  - bjoli 1y ago
    There are many languages out there that can grow the stack these days. If you have a language that can do tail recursion, it is really a very neat complement. In lisps it means being able to write a list building function in a direct consing way, and still being faster than the TCP-way.
- Jtsummers 1y ago
  Every recursive algorithm can be made into an iterative algorithm if you use an explicit stack instead of the implicit call stack. It's not always cleaner. In tail recursive algorithms, there is no stack, it's just a straight loop. def foo(state, acc): # if acc is needed if base-condition(state): return acc return foo(next(state), f(state, acc)) Is simply: def foo(state): acc = initial while not base-condition(state): acc = f(state, acc) state = next(state) return acc If it's not tail recursive you introduce a stack, for instance a DFS on a binary tree: def search(node, val): if node is None: return False # empty tree, only need this check once stack = [node] while stack: n = stack.pop() if n.val == val: return True if n.right: stack.push(n.right) if n.left: stack.push(n.left) return False Note the insertion order is reversed from the recursive calls in a typical DFS. We want left to be searched first and then its children and then we "recur" back to right and deal with its children, so we need to push right into the stack first and then left. When you have multiple mutually recursive functions (as is likely the case in a recursive descent parser) then things become more complicated, but it's still feasible.
javcasas 1y ago
Recursion deals with recursive data structures, and iteration deals with "plain old" data structures. When you use one to process the other, you get into trouble. For example, you need to manage a stack to do iteration on your binary tree. Or you need to construct slices to recurse on your arrays. It's all about ergonomics.
- dreamcompiler 1y ago
  This is overly simplistic. Is a binary tree recursive from the perspective of a type declaration? Yes. Is it recursive from the point of view of search? Depends. If you're doing depth-first search, then you need a stack and a recursive algorithm seems natural. If you're doing breadth-first search, then you need a queue and the algorithm is less obviously recursive. In either case the program could be expressed recursively or as an explicit loop. When a stack is needed, the underlying hardware always provides automatic stack management so recursion feels natural in that case. When a queue is needed it's more of a tossup since hardware and programming languages don't generally provide automatic queue management, so you're going to need to manage that data structure manually anyway. In which case whether you choose to use recursion or not is more of a personal preference.
  - javcasas 1y ago
    So a tree is easier to do recursing vs iterating in some cases, whereas in other cases recursion and iteration have roughly the same level of complexity. Kinda shows that recursive data structures are usually better dealt with recursion. Worst case you end up with the same level of difficulty as iteration.
    - busterarm 1y ago
      My career is practically built on the fact that other people 99% of the miss the simplest representation of the data/problem. Just look at myriad ways that people implement something like checking win conditions in Rock, Paper, Scissors. Switch statements, conditional hell, etc. ...you can just do something as simple as stick Rock, Scissors, Paper into a circular list and compare to the next element. It's practically readable as plain English. No programming skill required. If you need to code golf you can use modulo arithmetic, for a different kind of "simple", but then you lose readability.
Spivak 1y ago
I'm in your camp, recursive code is hard for the next reader, which might be you, to understand. It's a bit too magic looking for my taste. If you're looping it should look like a loop, if you're pushing onto a stack you should get to see the stack. It's also safe against modifications which might silently break the tail-call nature of it until you blow out the stack later. It also gives you much saner and more debuggable stack traces because all the state is in the current frame.
- busterarm 1y ago
  I never quite understood this recursion is hard/magic sentiment. Maybe it's because I started my CS education when it was still taught out of math departments or because it started with actually using programming languages to do algebra. Then again, the FP Kool-Aid is practically the blood in my veins at this point I guess.
  - hinkley 1y ago
    I’m good at spatial thinking, so on paper I should have zero issues with recursive code. But I also mentor and troubleshoot a lot and deep recursive code blows everyone’s mind. Even, it turns out, often the people who wrote it. Though they will swear otherwise. Self recursive code takes on a fractal nature - at any call stack you cannot determine the call depth. You are in a twisty little maze. When you layer calls horizontally, different tasks at different depths, it’s dead obvious where you are in the calculation. If all you can manage though is iteration, you still have the local variables to tell you where you are.
    - eru 1y ago
      I spend half my career with Haskell, OCaml, Erlang and we never had these problems with recursive code. (Or rather, we never had these problems and blamed it on recursion. We had to deal with plenty of bad code, of course.) In contrast, I remember plenty of problems stemming from mutation (and lack of static typing etc).
      - 1y ago
bjoli 1y ago
I am in the other camp. I prefer tail recursion and recursion over loops. However: For the simple cases it can and should probably be abstracted away like the racket for loops or my own goof-loop [1]. I just feel that a recursive calls makes state much more clear, but then again I am no fan of mutation in general. In my old python days I think a good 60% of my bugs were due to me being bad at managing state. [1] https://rikspucko.koketteriet.se/bjoli/goof-loop https://rikspucko.koketteriet.se/bjoli/goof-loop
- iamevn 1y ago
  I'm in the same boat, recursion tends to be easier for me to reason about because I'm expressing the problem in terms of some base case that incoming parameters are being reduced to rather than some condition that an iterative approach is working towards.
  - eru 1y ago
    I prefer recursion over loops. But even more I prefer abstracting away the recursion into combinators. One of my favourite combinators is matrix multiplication. You define what 'addition' and 'multiplication' mean in your case, and all of a sudden you get an algorithm that computes shortest paths in a graph or does regex matching. See https://news.ycombinator.com/item?id=9751987 https://news.ycombinator.com/item?id=9751987 But for more bread and butter cases, there's 'map' over various data structures, and 'reduce' and traversals of trees etc.
    - aeonik 1y ago
      I'm forbidden from those links :(
      - eru 1y ago
        Oh, that's a shame. However, if you do a websearch for 'fun with semirings' you can find the relevant publication. Or you can use the wayback machine or so?
deleted 1y ago
[deleted]
zelphirkalt 1y ago
I have my doubts about any CS class/lecture, that teaches, that the "iterative version is easier to scan". Might just be the bias or inexperience of the lecturer. By not I find recursive to be often easier to read than some for loop with its loop header and counter that I need to think about and update in my mind. And then the loop usually in many languages does not even have a return value, because it is not an expression, but a statement. Meeehhh, very meehhh in many languages. Not all, but many. I think maybe in languages like Ruby or Smalltalk a loop can be more readable, because of how they structure it as messages to objects, rather than special keywords in the language.
- hinkley 1y ago
  > I have my doubts about any CS class/lecture, that teaches, that the "iterative version is easier to scan". Well then you’re in luck because that was not an academic statement but a professional opinion - mine. You can’t optimize the patterns you can’t see because they’re obscured by accidental complexity. And iteration is a frequent trick I use to surface deeper pattern s.
  - bigDinosaur 1y ago
    Things like DFS add a lot of noise in the way of seeing the pattern IMO, but then again if you want explicit stack management and that's the pattern you want to see I suppose the iterative versions are clearer.
    - hinkley 1y ago
      I think this is in the same space as 'imperative shell, functional core'. Because what ends up happening is that in a tree or DAG you keep swapping back and forth between decision and action, and once the graph hits about 100 nodes only people who are very clever and very invested still understand it. A big win I mentioned elsewhere involved splitting the search from the action, which resulted in a more Dynamic Programming solution that avoided the need for cache and dealing with complex reentrancy issues. I'm sure there's another name for this but I've always just called this Plan and Execute. Plans are an easy 'teach a man to fish' situation. Sit at one breakpoint and determine if the bug is in the execution, the scan, or the input data. You don't need to involve me unless you think you found a bug or a missing feature. And because you have the full task list at the beginning you can also make decisions about parallelism that are mostly independent from the data structures involved. It's not so much enabling things that were impossible as enabling things that were improbable. Nobody was ever going to fix that code in its previous state. Now I had, and there were options for people to take it further if they chose.
pdpi 1y ago
> Tail recursion IME is a bigger foot gun This is true for some languages, but not all. E.g. scala has @tailrec annotations, which make it a compile error for the annotated function to not be tail recursive. Clojure doesn't have tail call elimination, but has the `recur` special form for explicit recursion that is guaranteed to not consume any stack space.Rust has reserved the `become` keyword that will eventually guarantee tail call elimination (So pretty similar to Clojure's recur, but I think Rust's version will allow mutual recursion) Zig goes the whole hog, and has `@call(modifier, fn, args)`, where `modifier` can be things like compile_time, always_tail, always_inline, never_tail, never_inline, and a bunch other desirable guarantees you might want.
- aw1621107 1y ago
  > Rust has reserved the `become` keyword that will eventually guarantee tail call elimination (So pretty similar to Clojure's recur, but I think Rust's version will allow mutual recursion) Support got added to nightly quite recently, in fact - on 2025-07-31 [0]. [0]: https://github.com/rust-lang/rust/pull/144232 https://github.com/rust-lang/rust/pull/144232
- LandR 1y ago
  Clojure has mutual recursion via (trampoline ...) https://clojuredocs.org/clojure.core/trampoline https://clojuredocs.org/clojure.core/trampoline
- phh 1y ago
  > > Tail recursion IME is a bigger foot gun > This is true for some languages, but not all. Useless anecdote that tail-recursive can be a foot gun even in Scala. I did a (screening) job interview at Datadog, they asked for "give the spare change back on that amount of money" exercise (simple variant), "in whichever language you want". I did my implementation in tail-recursive Scala (with the annotation). I ended up trying to explain that tail-recursivity doesn't explode in memory for the rest of the call (and failed)
  - pdpi 1y ago
    > I ended up trying to explain that tail-recursivity doesn't explode in memory for the rest of the call (and failed) I count that as a successful interview – They sent an interviewer who doesn't understand how tail recursion enables tail call elimination, and is either unwilling or unable to listen when is is explained to them. Sounds like the company would be a bad fit for somebody whose go-to approach is to implement the solution that way.
eru 1y ago
> Practically the day after I learned about tail recursion in CS class, I learned that almost all recursive calls can be translated to iteration, that in many cases the iterative version is easier to scan, is as fast if not faster, and that they can usually handle much much larger inputs than recursion due to avoiding stack overflow. What do you mean by easier to scan? I find (most) loops [0] hard to read, because they typically involve mutable state. When properly implemented, tail calls are as fast as gotos and loops, and don't blow up any stack. (Not all languages are implemented with a stack in any case.) However you have one point: Most of the time, we don't use recursion directly in our programs even in a language like Haskell or Scheme. Instead we define a 'combinator' that encapsulates the specific, limited recursion scheme that we want, and then use that one. This is very similar to how people generally don't use goto directly in their programs. You might be familiar with the combinators 'map', 'filter' and perhaps 'reduce'/'foldr'. You could re-interpret the various common loop types as such recursion combinators that weaker languages have to bake into their language, because they are not strong enough to express them as a user-defined library. And indeed, Haskell has Control.Monad.Loops (https://hackage.haskell.org/package/monad-loops-0.4.3/docs/Control-Monad-Loops.html https://hackage.haskell.org/package/monad-loops-0.4.3/docs/C...) which gives you exactly the common loop types as a library. Some examples of less common combinators are eg 'unfold' or various combinators to traverse trees or graphs. [0] The foreach-loop over some sequence is less headache inducing than eg a while-loop.
akdor1154 1y ago
There are cases where iteration is clearer, and there are cases where recursion is clearer. It's well worth being familiar with both - if you learn how to shoehorn both approaches where they aren't ideal, your judgement on avoiding such practices will improve. :)
rr808 1y ago
> IME is a bigger foot gun than Pretty much true for any functional feature. Great in the classroom, less practical in the real world.
- SJC_Hacker 1y ago
  Trying to be as functional as possible I think has great benefits in the "real world". Functions are very easy to unit test, for one. Pure functional is difficult, but breaking out the parts of the program which can be pure functional is generally a smart thing to do If I had drive and ability the to make a programming language from scratch, it would be hybrid imperative/functional, and "pure" functions (no side effects, EXCEPT possibly debug logging) would be clearly marked as such.
  - alternatex 1y ago
    Pure functional isn't too difficult once you understand how to put everything that causes side effects on the side. You can write a domain layer in a purely functional manner and feed it data from non-pure sources. It's definitely a shift in thinking for people used to something like OOP, but once you make it, writing software functionally is not difficult. There's really not many ways to approach it, unlike OOP for which there are hundreds of books and approaches.
    - William_BB 1y ago
      I studied FP in college. I currently work on a large low latency C++ codebase. I honestly have no idea how I'd use pure functional concepts everywhere in this context. I'm also probably doing it wrong.
      - alternatex 1y ago
        I wouldn't be able to say without knowing the project, but just following the simple rule of not calling impure functions from pure functions will force your codebase in a state where all impure functions bubble up to the top layer of calling code. For web apps that's simple, it's just the entry point of an HTTP request. For desktop apps it might mean the event handlers for user actions. Then you realize you are sort of forced to handle all exceptions from impure code at the top level, and after that all that remains is validated data running through pure functions that are easily testable. At the top layer, your code will dip in and out of pure and impure functions. All possible exceptions coming from bad data and I/O issues are visible at that layer since those cannot reasonably occur in the pure code. I admit it will be an odd sight at first, but the feeling of working with a domain safe from bad data makes it worth it.

tombert 1y ago

In my mind, the biggest advantage to using tail recursion over vanilla loops is the ability to keep using persistent data structures without any (apparent) mutation. At least in theory, a tail recursive call will be converted into a dumb jump, so there shouldn't be a performance penalty, but since from your code's perspective you're passing in the stuff for the next iteration, you can keep using the pretty and easy-to-reason-about structures without creating any kind of mutable reference. I'm not 100% sold on tail recursion in a broader sense, but at least with Clojure's loop/recur stuff it is kind of cool to be able to keep using persistent data structures across iterations of loops.

weitendorf 1y ago
What makes tail recursion "special" is that there exists a semantically equivalent mutable/iterative implementation to something expressed logically as immutable/recursive. [0] Of course, this means that the same implementation could also be directly expressed logically in a way that is mutable/iterative. func pow(uint base, uint n): n == 0 ? return 1 : return n * pow(base, n-1) is just func pow(uint base, uint n): uint res = 1; for(i=0; i<n; i++){ res *= n} return res There is no real "advantage" to, or reason to "sell" anybody on tail call recursion if you are able to easily and clearly represent both implementations, IMO. It is just a compiler/runtime optimization, which might make your code more "elegant" at the cost of obfuscating how it actually runs + new footguns from the possibility that code you think should use TCO actually not (because not all immutable + recursive functions can use TCO, only certain kinds, and your runtime may not even implement TCO in all cases where it theoretically should). As an aside, in C++ there is something very similar to TCO called copy-elision/return-value-optimization (RVO): [1]. As with TCO it is IMO not something "buy into" or sell yourself on, it is just an optimization you can leverage when structuring your code in a way similar to what the article calls "continuation passing style". And just like TCO, RVO is neat but IMO slightly dangerous because it relies on implicit compiler/runtime optimizations that can be accidentally disabled or made non-applicable as code changes: if someone wanders in and makes small semantic to changes to my code relying on RVO/TCO for performance they could silently break something important. [0] EXCEPT in practice all implementation differences/optimizations introduce observable side effects that can otherwise impact program correctness or semantics. For example, a program could (perhaps implicitly) rely on the fact that it errors out due to stack overflow when recursing > X times, and so enabling TCO could cause the program to enter new/undesirable states; or a program could rely on a functin F making X floating point operations taking at least Y cycles in at least Z microseconds, and not function properly when F takes less than Z microseconds after enabling vectorization. This is Hyrum's Law [2]. [1] https://en.wikipedia.org/wiki/Copy_elision#Return_value_optimization https://en.wikipedia.org/wiki/Copy_elision#Return_value_opti... [2] https://www.hyrumslaw.com/ https://www.hyrumslaw.com/
- gleenn 1y ago
  I would argue having the parameters that change during the loop be explicit is a very nice advantage. Agree that the things can be equivalent in terms of execution but the readability and explicitness, and the fact that all the parameters are listed in the same place is great.
  - weitendorf 1y ago
    Agreed. Some people really like FP a lot, and I think it's underrated that the kinds of functions where TCO is applicable tend to be so simple that they are not really that inelegant when expressed imperatively. My true opinion is that relying on TCO is usually choosing ideological adherence to FP (or "code that looks cooler") over reliability/performance/communication. That said, just as I'd expect experienced C++ programmers to be able to recognize others' code using RVO and be careful not to restructure things to break it, I'd concede that experienced FP programmers might be unlikely to accidentally break others' TCO. It's just that ad absurdum you cannot expect every developer to be able to read every other developers' mind and recognize/workaround all implicit behavior they encounter.
    - eru 1y ago
      > [...] and I think it's underrated that the kinds of functions where TCO is applicable tend to be so simple that they are not really that inelegant when expressed imperatively. I suspect you are only thinking of patterns that are basically equivalent to a loop. I might agree with that. TCO really shines when you want to implement state machines. See eg https://news.ycombinator.com/item?id=43076088 https://news.ycombinator.com/item?id=43076088 for an example where using tail calls in Python's interpreter loop gives nice performance benefits. Similar also for LUA. > [...] I'd concede that experienced FP programmers might be unlikely to accidentally break others' TCO. Compiler (or linter) checkable annotations would help here. You are right that you want to make it possible for programmers to statically assert somehow that their function call is a tail call. Btw this reminds me: recursion isn't just something you do in computation, but also in data structures (amongst other things). In eg Rust the members of your data structure are typically just laid out one after another, but when you have a recursive structure (and in certain other cases) you need to box it, otherwise you'd get an infinitely large data structure. Boxing is more or less equivalent to using indirection via a pointer. However, unboxing isn't really like TCO. It's more like in-lining.
ramchip 1y ago
I think you're confusing mutation and variable reassignment?
- tombert 1y ago
  I'm saying that if I do a regular loop, something needs to explicitly mutate, either a reference or a value itself. `for (var i = 0; i < n, i++)`, for example, requires that `i` mutate in order to keep track of the value so that the loop can eventually terminate. You could also do something like: var i = new Obj(); while (!i.isDone()) { //do some stuff i = new Obj(); } There, the reference to `i` is being mutated. For tail recursion, it's a little different. If I did something like Factorial: function factorial(n, acc) { if (n <= 1) return acc; return factorial(n - 1, acc * n); } Doing this, there's no explicit mutation. It might be happening behind the scenes, but everything there from the code perspective is creating a new value. In something like Clojure, you might do something like (defn vrange [n] (loop [i 0 v []] (if (< i n) (recur (inc i) (conj v i)) v))) (stolen from [1]) In this case, we're creating "new" structures on every iteration of the loop, so our code is "more pure", in that there's no mutation. It might be being mutated in the implementation but not from the author's perspective. I don't think I'm confusing anything. [1] https://clojure.org/reference/transients https://clojure.org/reference/transients
  - eru 1y ago
    You could imagine a language like eg Python with a for-each loop that creates a new variable for each run through the loop body. Basically, just pretend the loop body is a lambda that you call for each run through the loop. It might make sense to think of the common loops as a special kind of combinator (like 'map' and 'filter', 'reduce' etc.) And just like you shouldn't write everything in terms of 'reduce', even though you perhaps could, you shouldn't write everything in terms of the common loops either. Make up new combinators, when you need them. For comparison, in Haskell we seldom use 'naked' recursion directly: we typically define a combinator and then use it. That often makes sense, even if you only use the combinator once.
  - ramchip 1y ago
charcircuit 1y ago
>without creating any kind of mutable reference. The parameter essentially becomes a mutable reference.
- tombert 1y ago
  No disagreement on that but that's an implementation detail and from the coder's perspective there's no mutable references.
  - charcircuit 1y ago
    From the coder's perspective it is. There's just different syntax for assigning to them.
    - tombert 1y ago
      No, from the coder's perspective it looks like I'm passing an argument into a function. I suppose you could say that arguments in general are "mutable references", and I guess that's not necessarily "untrue", but that's not generally how I visualize it. If I pass a persistent structure into a tail call, it looks like I'm passing a copy into there, in the same way that I might if I did something like `Math.abs(myValue * 3)`; the compiler converts it to a mutable reference but I see it as the same as passing a value.
  - weitendorf 1y ago
    From the coder's perspective, there are no mutable references only if the coder does not really rely on or care about the possibility that their code uses TCO. If they actively want TCO then they definitely care about the performance benefits they get from underlying mutability/memory reuse/frame elision.
    - tombert 1y ago
      Yeah but that's why I prefer Clojure's loop/recur thing. You're not allowed to have non-tail recursion there, so it's not implicit, so you really can pretend that there's no mutable references.

CalChris 1y ago

I must have missed this class. How does one convert a recursive descent parser into an iterative one?

pmg101 1y ago
https://news.ycombinator.com/item?id=44837949 https://news.ycombinator.com/item?id=44837949
jandrese 1y ago
By making your own stack and using loops.
kylec 1y ago
You can do it by managing your own stack, but I would argue that doing so makes the algorithm LESS easy to scan and has its own sets of problems.
electroly 1y ago
Same way as any other algorithm: with an explicit heap-allocated stack. I have a naive parser where I built operator precedence into the grammar as nested productions instead of using an algorithm like shunting yard. An input of ((((((1)))))) blew the stack. Converted it to an explicit stack and it was fine; deep for the call stack was not deep for my own heap-allocated stack. Nasty code, though--I think this serves as one of the counterexamples to the idea that the recursive code gets simpler when turning it into iteration. The original OP was talking more specifically about tail recursion, which a recursive descent parser won't be.
- bjoli 1y ago
  There are many languages out there that can grow the stack these days. If you have a language that can do tail recursion, it is really a very neat complement. In lisps it means being able to write a list building function in a direct consing way, and still being faster than the TCP-way.
Jtsummers 1y ago
Every recursive algorithm can be made into an iterative algorithm if you use an explicit stack instead of the implicit call stack. It's not always cleaner. In tail recursive algorithms, there is no stack, it's just a straight loop. def foo(state, acc): # if acc is needed if base-condition(state): return acc return foo(next(state), f(state, acc)) Is simply: def foo(state): acc = initial while not base-condition(state): acc = f(state, acc) state = next(state) return acc If it's not tail recursive you introduce a stack, for instance a DFS on a binary tree: def search(node, val): if node is None: return False # empty tree, only need this check once stack = [node] while stack: n = stack.pop() if n.val == val: return True if n.right: stack.push(n.right) if n.left: stack.push(n.left) return False Note the insertion order is reversed from the recursive calls in a typical DFS. We want left to be searched first and then its children and then we "recur" back to right and deal with its children, so we need to push right into the stack first and then left. When you have multiple mutually recursive functions (as is likely the case in a recursive descent parser) then things become more complicated, but it's still feasible.

javcasas 1y ago

Recursion deals with recursive data structures, and iteration deals with "plain old" data structures. When you use one to process the other, you get into trouble. For example, you need to manage a stack to do iteration on your binary tree. Or you need to construct slices to recurse on your arrays. It's all about ergonomics.

dreamcompiler 1y ago
This is overly simplistic. Is a binary tree recursive from the perspective of a type declaration? Yes. Is it recursive from the point of view of search? Depends. If you're doing depth-first search, then you need a stack and a recursive algorithm seems natural. If you're doing breadth-first search, then you need a queue and the algorithm is less obviously recursive. In either case the program could be expressed recursively or as an explicit loop. When a stack is needed, the underlying hardware always provides automatic stack management so recursion feels natural in that case. When a queue is needed it's more of a tossup since hardware and programming languages don't generally provide automatic queue management, so you're going to need to manage that data structure manually anyway. In which case whether you choose to use recursion or not is more of a personal preference.
- javcasas 1y ago
  So a tree is easier to do recursing vs iterating in some cases, whereas in other cases recursion and iteration have roughly the same level of complexity. Kinda shows that recursive data structures are usually better dealt with recursion. Worst case you end up with the same level of difficulty as iteration.
  - busterarm 1y ago
    My career is practically built on the fact that other people 99% of the miss the simplest representation of the data/problem. Just look at myriad ways that people implement something like checking win conditions in Rock, Paper, Scissors. Switch statements, conditional hell, etc. ...you can just do something as simple as stick Rock, Scissors, Paper into a circular list and compare to the next element. It's practically readable as plain English. No programming skill required. If you need to code golf you can use modulo arithmetic, for a different kind of "simple", but then you lose readability.

Spivak 1y ago

I'm in your camp, recursive code is hard for the next reader, which might be you, to understand. It's a bit too magic looking for my taste. If you're looping it should look like a loop, if you're pushing onto a stack you should get to see the stack. It's also safe against modifications which might silently break the tail-call nature of it until you blow out the stack later. It also gives you much saner and more debuggable stack traces because all the state is in the current frame.

busterarm 1y ago
I never quite understood this recursion is hard/magic sentiment. Maybe it's because I started my CS education when it was still taught out of math departments or because it started with actually using programming languages to do algebra. Then again, the FP Kool-Aid is practically the blood in my veins at this point I guess.
- hinkley 1y ago
  I’m good at spatial thinking, so on paper I should have zero issues with recursive code. But I also mentor and troubleshoot a lot and deep recursive code blows everyone’s mind. Even, it turns out, often the people who wrote it. Though they will swear otherwise. Self recursive code takes on a fractal nature - at any call stack you cannot determine the call depth. You are in a twisty little maze. When you layer calls horizontally, different tasks at different depths, it’s dead obvious where you are in the calculation. If all you can manage though is iteration, you still have the local variables to tell you where you are.
  - eru 1y ago
    I spend half my career with Haskell, OCaml, Erlang and we never had these problems with recursive code. (Or rather, we never had these problems and blamed it on recursion. We had to deal with plenty of bad code, of course.) In contrast, I remember plenty of problems stemming from mutation (and lack of static typing etc).
    - 1y ago

bjoli 1y ago

I am in the other camp. I prefer tail recursion and recursion over loops. However: For the simple cases it can and should probably be abstracted away like the racket for loops or my own goof-loop [1]. I just feel that a recursive calls makes state much more clear, but then again I am no fan of mutation in general. In my old python days I think a good 60% of my bugs were due to me being bad at managing state. [1] https://rikspucko.koketteriet.se/bjoli/goof-loop https://rikspucko.koketteriet.se/bjoli/goof-loop

iamevn 1y ago
I'm in the same boat, recursion tends to be easier for me to reason about because I'm expressing the problem in terms of some base case that incoming parameters are being reduced to rather than some condition that an iterative approach is working towards.
- eru 1y ago
  I prefer recursion over loops. But even more I prefer abstracting away the recursion into combinators. One of my favourite combinators is matrix multiplication. You define what 'addition' and 'multiplication' mean in your case, and all of a sudden you get an algorithm that computes shortest paths in a graph or does regex matching. See https://news.ycombinator.com/item?id=9751987 https://news.ycombinator.com/item?id=9751987 But for more bread and butter cases, there's 'map' over various data structures, and 'reduce' and traversals of trees etc.
  - aeonik 1y ago
    I'm forbidden from those links :(
    - eru 1y ago
      Oh, that's a shame. However, if you do a websearch for 'fun with semirings' you can find the relevant publication. Or you can use the wayback machine or so?

deleted 1y ago

[deleted]

zelphirkalt 1y ago

I have my doubts about any CS class/lecture, that teaches, that the "iterative version is easier to scan". Might just be the bias or inexperience of the lecturer. By not I find recursive to be often easier to read than some for loop with its loop header and counter that I need to think about and update in my mind. And then the loop usually in many languages does not even have a return value, because it is not an expression, but a statement. Meeehhh, very meehhh in many languages. Not all, but many. I think maybe in languages like Ruby or Smalltalk a loop can be more readable, because of how they structure it as messages to objects, rather than special keywords in the language.

hinkley 1y ago
> I have my doubts about any CS class/lecture, that teaches, that the "iterative version is easier to scan". Well then you’re in luck because that was not an academic statement but a professional opinion - mine. You can’t optimize the patterns you can’t see because they’re obscured by accidental complexity. And iteration is a frequent trick I use to surface deeper pattern s.
- bigDinosaur 1y ago
  Things like DFS add a lot of noise in the way of seeing the pattern IMO, but then again if you want explicit stack management and that's the pattern you want to see I suppose the iterative versions are clearer.
  - hinkley 1y ago
    I think this is in the same space as 'imperative shell, functional core'. Because what ends up happening is that in a tree or DAG you keep swapping back and forth between decision and action, and once the graph hits about 100 nodes only people who are very clever and very invested still understand it. A big win I mentioned elsewhere involved splitting the search from the action, which resulted in a more Dynamic Programming solution that avoided the need for cache and dealing with complex reentrancy issues. I'm sure there's another name for this but I've always just called this Plan and Execute. Plans are an easy 'teach a man to fish' situation. Sit at one breakpoint and determine if the bug is in the execution, the scan, or the input data. You don't need to involve me unless you think you found a bug or a missing feature. And because you have the full task list at the beginning you can also make decisions about parallelism that are mostly independent from the data structures involved. It's not so much enabling things that were impossible as enabling things that were improbable. Nobody was ever going to fix that code in its previous state. Now I had, and there were options for people to take it further if they chose.

pdpi 1y ago

> Tail recursion IME is a bigger foot gun This is true for some languages, but not all. E.g. scala has @tailrec annotations, which make it a compile error for the annotated function to not be tail recursive. Clojure doesn't have tail call elimination, but has the `recur` special form for explicit recursion that is guaranteed to not consume any stack space.Rust has reserved the `become` keyword that will eventually guarantee tail call elimination (So pretty similar to Clojure's recur, but I think Rust's version will allow mutual recursion) Zig goes the whole hog, and has `@call(modifier, fn, args)`, where `modifier` can be things like compile_time, always_tail, always_inline, never_tail, never_inline, and a bunch other desirable guarantees you might want.

aw1621107 1y ago
> Rust has reserved the `become` keyword that will eventually guarantee tail call elimination (So pretty similar to Clojure's recur, but I think Rust's version will allow mutual recursion) Support got added to nightly quite recently, in fact - on 2025-07-31 [0]. [0]: https://github.com/rust-lang/rust/pull/144232 https://github.com/rust-lang/rust/pull/144232
LandR 1y ago
Clojure has mutual recursion via (trampoline ...) https://clojuredocs.org/clojure.core/trampoline https://clojuredocs.org/clojure.core/trampoline
phh 1y ago
> > Tail recursion IME is a bigger foot gun > This is true for some languages, but not all. Useless anecdote that tail-recursive can be a foot gun even in Scala. I did a (screening) job interview at Datadog, they asked for "give the spare change back on that amount of money" exercise (simple variant), "in whichever language you want". I did my implementation in tail-recursive Scala (with the annotation). I ended up trying to explain that tail-recursivity doesn't explode in memory for the rest of the call (and failed)
- pdpi 1y ago
  > I ended up trying to explain that tail-recursivity doesn't explode in memory for the rest of the call (and failed) I count that as a successful interview – They sent an interviewer who doesn't understand how tail recursion enables tail call elimination, and is either unwilling or unable to listen when is is explained to them. Sounds like the company would be a bad fit for somebody whose go-to approach is to implement the solution that way.

eru 1y ago

> Practically the day after I learned about tail recursion in CS class, I learned that almost all recursive calls can be translated to iteration, that in many cases the iterative version is easier to scan, is as fast if not faster, and that they can usually handle much much larger inputs than recursion due to avoiding stack overflow. What do you mean by easier to scan? I find (most) loops [0] hard to read, because they typically involve mutable state. When properly implemented, tail calls are as fast as gotos and loops, and don't blow up any stack. (Not all languages are implemented with a stack in any case.) However you have one point: Most of the time, we don't use recursion directly in our programs even in a language like Haskell or Scheme. Instead we define a 'combinator' that encapsulates the specific, limited recursion scheme that we want, and then use that one. This is very similar to how people generally don't use goto directly in their programs. You might be familiar with the combinators 'map', 'filter' and perhaps 'reduce'/'foldr'. You could re-interpret the various common loop types as such recursion combinators that weaker languages have to bake into their language, because they are not strong enough to express them as a user-defined library. And indeed, Haskell has Control.Monad.Loops (https://hackage.haskell.org/package/monad-loops-0.4.3/docs/Control-Monad-Loops.html https://hackage.haskell.org/package/monad-loops-0.4.3/docs/C...) which gives you exactly the common loop types as a library. Some examples of less common combinators are eg 'unfold' or various combinators to traverse trees or graphs. [0] The foreach-loop over some sequence is less headache inducing than eg a while-loop.

akdor1154 1y ago

There are cases where iteration is clearer, and there are cases where recursion is clearer. It's well worth being familiar with both - if you learn how to shoehorn both approaches where they aren't ideal, your judgement on avoiding such practices will improve. :)

rr808 1y ago

> IME is a bigger foot gun than Pretty much true for any functional feature. Great in the classroom, less practical in the real world.

SJC_Hacker 1y ago
Trying to be as functional as possible I think has great benefits in the "real world". Functions are very easy to unit test, for one. Pure functional is difficult, but breaking out the parts of the program which can be pure functional is generally a smart thing to do If I had drive and ability the to make a programming language from scratch, it would be hybrid imperative/functional, and "pure" functions (no side effects, EXCEPT possibly debug logging) would be clearly marked as such.
- alternatex 1y ago
  Pure functional isn't too difficult once you understand how to put everything that causes side effects on the side. You can write a domain layer in a purely functional manner and feed it data from non-pure sources. It's definitely a shift in thinking for people used to something like OOP, but once you make it, writing software functionally is not difficult. There's really not many ways to approach it, unlike OOP for which there are hundreds of books and approaches.
  - William_BB 1y ago
    I studied FP in college. I currently work on a large low latency C++ codebase. I honestly have no idea how I'd use pure functional concepts everywhere in this context. I'm also probably doing it wrong.
    - alternatex 1y ago
      I wouldn't be able to say without knowing the project, but just following the simple rule of not calling impure functions from pure functions will force your codebase in a state where all impure functions bubble up to the top layer of calling code. For web apps that's simple, it's just the entry point of an HTTP request. For desktop apps it might mean the event handlers for user actions. Then you realize you are sort of forced to handle all exceptions from impure code at the top level, and after that all that remains is validated data running through pure functions that are easily testable. At the top layer, your code will dip in and out of pure and impure functions. All possible exceptions coming from bad data and I/O issues are visible at that layer since those cannot reasonably occur in the pure code. I admit it will be an odd sight at first, but the feeling of working with a domain safe from bad data makes it worth it.