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

[2] https://www.hyrumslaw.com/

I think you're confusing mutation and variable reassignment?

    var i = new Obj(); 
    while (!i.isDone()) {
        //do some stuff
        i = new Obj(); 
    }

    function factorial(n, acc) {
        if (n <= 1) return acc;
        return factorial(n - 1, acc * n);
    }
    

    (defn vrange [n]
      (loop [i 0 v []]
        (if (< i n)
          (recur (inc i) (conj v i))
          v)))

>without creating any kind of mutable reference.

The parameter essentially becomes a mutable reference.

By making your own stack and using loops.

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.

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.

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.

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.

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.

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.

I know that's the origin of why Clojure does its manual loop/recur thing, but I've grown to kind of prefer its explicitness. There's no ambiguity on whether it will TCO; it simply won't compile if it's not tail-call.

I don't agree that being able to turn off TCO in debugging is enough to call Guido's characterization "ridiculous". I often have to debug running production systems, and those are (hopefully) not deployed with debug compilations.

You're not wrong about loops not creating a stack trace; I guess what bothers me (and maybe Guido) is that with loops there's no expectation of a stack trace, while with a function call there is.

> It is also true that loops mess up your stack traces

No, because an indirect tail-call eliminates the calling frame. After, it looks like the caller of that function called a function it did not call. In fact, with tail-calls a whole pile of steps gets telescoped down to nothing[1]. This is not the case with a loop, it doesn't jump to itself indirectly. Loops don't jump into the middle of other loops in other functions. We can still follow the chain of control flow from the start of the main function, through (non-tail) calls, i.e. the stack, through the start of the loop, and then from some backedge in the loop body we're looking at.

Tail-calls are absolutely harder to debug in general than loops.

[1] In the limit, if the entire program was transformed into CPS with tail-calls everywhere, the original execution stack is now strewn throughout the heap as a chain of closures.