Comment by hinkley

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

RVO and URVO are slightly different from TCO in that’s the language guarantees that they are required to happen. You are correct though that small changes can accidentally turn it off unintentionally.

With Named RVO (I.e. you explicitly `return named_variable;`) copy-elision is actually guaranteed by the standard. I believe returning the return value of a function call is also guaranteed to not do a copy constructor. Anything else is compiler and optimization level dependent.

> func pow(uint base, uint n): n == 0 ? return 1 : return n * pow(base, n-1)

Nitpick: that’s not tail recursive. Something like def pow(base, n, acc=1) = match n case 0 => acc; default => pow(base, n-1, acc*base)

> Of course, this means that the same implementation could also be directly expressed logically in a way that is mutable/iterative.

Yes, compilers exist.

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

Avoiding mutation avoids headaches.

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

These programs are likely not standards compliant. (And that's not just true for the C++ standard but for basically any language with a standard.)

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

Who says TCO has to be always implicit? In eg Scheme it's explicit in the standard, and in other languages you can have annotations.

(Whether a call is in tail position is more or less a property you can ascertain syntactically, so your annotation doesn't even have to be understood by the compiler: the linter is good enough. That would catch your 'accidental changes' part.

Things get more complicated, when you have implicit clean-ups happen after returning from the function. Like calling destructors in C++. Then the function call is arguably not in a tail position anymore, and so TCO doesn't apply. Whether this is detectable reliably at compile time depends on the details of your language.)

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.

To nitpick a bit, NRVO is an optimization as there is no guarantee that it will be performed, but RVO is now guaranteed (you can now return temporary non-copyable /non-movable objects for example).

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

Nope. Loops are unnecessary unless you have mutation. If you don't mutate, there's no need to run the same code again: if the state of the world did not change during iteration 1, and you run the same code on it again, the state of the world won't change during iteration 2.

No. There's no mutation happening.

Of course, a compiler might do whatever shenanigans it has to do. But that's an implementation detail and doesn't change how the language works.

(And let's not pretend that CPUs execute something that resembles an imperative language like C under the hood. That might have been true during the PDP11 or a VAX days. These days with out-of-order execution, pipelining etc what's actually happening doesn't really resemble one-after-another imperative code much.)

If it does, then you would be able to express a race condition with it.

EDIT: I re-read parent comment.

>> the biggest advantage to using tail recursion over vanilla loops is the ability to keep using persistent data structures without any (apparent) mutation.

Yes

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

There's the implied mutation.

No disagreement on that but that's an implementation detail and from the coder's perspective there's no mutable references.

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

But for more bread and butter cases, there's 'map' over various data structures, and 'reduce' and traversals of trees etc.

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.

Sometimes the messy translation into an explicit stack and dispatch loop is necessary, if you want to pause the calculation, serialize the current state, and reconstitute it later. (E.g., if you want to add disk-saved checkpoints, a frequent hassle in some of my projects.) Coroutines can get you the equivalent of pausing and resuming for a recursive routine, but I'm not aware of any language that lets you serialize the call stack.

If you have to use an explicit stack, you're still doing recursion. Useful if you're implementing the Ackermann function in FORTRAN 77, I suppose. Unless you're worried about running out of stack space, it's generally easier to reason about if you just use regular recursion.

That only applies for non-primitive recursive functions, though. Most people rarely encounter those. For primitive recursive functions, it's all down to the nature of the function and what's idiomatic for your language. If you're using Scheme, for example, recursion is the name of the game.

When TCO recursion was first developed it was very explicitly called out as a syntactic and structurally improved GOTO but still fundamentally a GOTO that could take params.

Recursion isn't physically real, any book that teaches the abstraction before explaining either the call stack (for non-TCO recursion) or in the GOTO context is a book actively trying to gatekeeper CS and weed out readers. (Not that any of those old pascal turbo/boreland books from the 90s actually shipped code that compiled.)

I had several people on HN of all places try to "teach me" recursion after this simple line inside a larger comment:

> It's like acting like recursion is physically real (it's not) when it smuggles in the call stack.

Recursion IS real abstractly. It's just not physically real, it was developed before we knew how DNA/RNA encoding handles the same issues in a more performant way.

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.

TCO stands for "TAIL call optimization". It will obviously not save your arse if the call is not in the tail of the function, exactly the same as "python generators will not help you if you are doing C++".

> When a stack is needed, the underlying hardware always provides automatic stack management so recursion feels natural in that case.

Not true at all. Eg Risc-V provides no stack management at all. But compilers and interpreters exist, so it doesn't make a difference to how your high level code 'feels'.

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.

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.

I have seen this quite often. I blame it on the obsession with UML along with the limitations of UML. I/E in UML every one draws boxes that have arrows to other boxes, but no one draws boxes that have boxes inside them. Instead, you draw a box with an arrow going out and then back to itself, hence _it has to be a loop because the arrow does a loop_.

That's why React components are _weird and wrong_, SQL CTEs are _overly complicated_, and functional programming is _impossible to understand_. It's all boxes with other boxes inside them, instead of next to them, and many people can't understand you can nest boxes many times.

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.