I think the difference between recursion and looping is that the former requires you to be very explicit about the state you intend to modify and persist between iterations, while it's generally somewhat of a free-for-all in imperative loops.

The most common looping construct I see in clojure is the for statement

Which isn't quite the free for all it is in traditional languages

You have to be very conscious and coding against the grain to use it to bang on values in place

This is a general design principle that I appreciate about the Lisp family of languages in general. You can write highly imperative code that mutates things in-place, but it's a little harder to do and it's something you do only when you really need to do it. Whereas the default idioms are functional, and functional design is the path of least resistance. Perl is morally the opposite of functional programming in many ways, but I actually think this design is a great embodiment of the "make easy things easy, make hard things possible" ethos of Larry Wall.

I mostly agree, and proponents of FP shouldn't stress the recursion too much.

When I program in Haskell, I rarely use recursion myself. Most loops are just maps and folds. Need to build another structure from existing structure? Foldl'. Once I understood that the value being folded can be arbitrarily complex, FP became simpler (but terser) than iterative programming for me.

Agreed, I rarely reach for recursion myself when developing. Most of my transformations are map, filter, and reduce. Although from time to time, I will combine them with recursion when necessary. I find recurring from a reducing function to be great for traversing or searching trees or other recursive data structures. Usually these are accompanied by a ton of comments for the next developer. :)

I don't think of map operations as loops. Instead as parallel operations on elements of a list works as a better mental model for me.

When learning them coming from an imperative background, it's inevitable to start with that idea, but somehow feels like a limiting model.

Maybe it's my background but recursion feels more natural, either you are at the base, or at a point with N-1 items below. This gives you two different invariants that you can use to simplify the code.

Small example, though not exactly comparable to looping.

I needed to create a human readable qualified path appended by a hash (to avoid conflicts). This qualified path was needed ahead of the construction of an object, and the logical name must have been used in both the hash and qualified path as it was global (Yes, it was an S3 bucket).

I wrote a function

     uniqueQualifiedName: Construct x Optional(logicalId) x Properties -> string.

The recursive step is at the top, where the logicalId is transformed to a construct in the scope of the first argument, and the function is called again with NewConstruct x Nothing x Properties. This could easily be adjusted to work with a list of logicalIds instead.

The invariant in the recursive step is that once the call returns, the construct at the end of the chain will be exactly the construct I inserted, and I can pop it safely, and the scope object will be none the wiser.

The invariant in the base is simply that I don't need to worry about logicalId being anything.

You can see then how easy it is to adapt this to work with a list, whereas with a loop you'd have to write it from zero, and then roll back. Too messy imho.

I don't understand your problem or your solution, but that seems like a lot of things going on to construct a string.

But it sounds like you could just bash the logicalIds together and append the hash of the bash of the mash. Might not need loops or recursion.

To just bash them together I'd have to either use the private api which is not a good thing. Alternatively I can push a list of items N steps to each object and have each one of them both adding and removing the logical names.

> Nobody has yet convinced me that recursion has any sustained advantage over looping.

Looping may require trampolining or defunctionalisation, whilst recursion can be written much more directly and simply. As a very simple example (in pseudocode):

  even(n: uint): boolean = n match {
    case 0: true
    case n: odd(n-1)
  }

  odd(n: uint): boolean = n match {
    case 0: false
    case n: even(n-1)
  }

Whilst these are pretty silly implementations of odd & even, I don't know of a direct analogue using loops. For more realistic examples, just look at any "main loop"; AKA "trampoline boilerplate to work-around our language's lack of tail-call elimination" ;)

    for(range(n)):
        is_true = !is_true

And adjust for all the off by 1 errors. You're managing the same amount of state both ways, but with the loop all the state mutation lives on one line instead of spread throughout a stack.

That's not a "direct analogue" of my implementation, for many reasons; you've changed the semantics and engineering tradeoffs so much that we might as well write `n % 2 == 0`.

The biggest problem is that, assuming we copy your snippet into a couple of function definitions, we've completely lost the encapsulation/separation-of-concerns/delegation/etc. provided by my `odd` and `even` functions; i.e. all of the "software engineering" stuff that makes source code more maintainable than disassembled binary.

Your loop is more like the following, which is not what I wrote:

  even(n: uint): boolean = n match {
    case 0: true
    case n: !even(n-1)
  }

  odd(n: uint): boolean = n match {
    case 0: false
    case n: !odd(n-1)
  }

The major difference is the use of iteration/tail-recursion in this implementation:

- This loop collapses all of the abstraction, forcing each function to implement the entire solution. In contrast, my implementation uses divide-and-conquer: only the zero case is handled directly, and the non-zero case is delegated to a more suitable handler.

- Wrapping two copies of this loop into `even` and `odd` functions will completely lose the relationships inherent in my implementation. For example, if we add instrumentation, optimisations, logging, etc. to the `even` function, that will affect my `odd` function but have no effect if we were to write independent loops.

- This looping implementation has extra dependencies, specifically on `range` and `!`. The `!` function requires knowledge of boolean algebra, the `range` function requires knowledge of lists/sequences/iterators, and `range` also seems to make more sophisticated use of number theory than the `odd`/`even`/`-` required to understand and maintain my implementation.

Note that I'm not claiming either of these is "better"/"worse" than the other. Simply that your loop is not representative of my example; that's specifically why I chose a mutually-recursive example, and not an iterative/tail-recursive one!

(Of course, all of these are exaggerations for such a simple example; but complex, real-world codebases require such engineering practices and tradeoffs to be taken seriously for the sake of maintenance)

I see, so the point you wanted to draw was that if you wanted to implement two functions, mutual recursion might let you separate the implementation logic. That is a nice trick.

> you've changed the semantics and engineering tradeoffs so much that we might as well write `n % 2 == 0`.

That is a fairly glaring weakness of the example you've chosen - it is taking a simple situation and overthinking it. It doesn't really matter because I see your point and surely one would exist, but do you have an example where this technique is an efficient solution?

Yes, exactly :) Again, it's not always "better", but it's a situation that doesn't seem to map directly to a loop.

I gave a more complicated, realistic example in a sibling comment https://news.ycombinator.com/item?id=35466256

It's heretic and beside the point, but:

    bool odd(uint n){return n&1;} bool even(uint n){ return !odd(n);}

I can't help but think in terms of classic CPU.

    fun odd (n: Uint32) -> Bool =
        let Uint32(n0, _, _, _) = n in
        let Byte(b0, _, _, _, _, _, _, _) = n0 in
        b0

Who needs hardware support for integers anyway? If you want a two-complement arithmetic, you can build it yourself (although presumably it'll be in the standard library).

Here's how I would write the loop version of this. It does involve an optimization since we know parity only depends on n - 1.

  #include <algorithm>
  
  template <typename T>
  bool even(T n)
  {
      bool is_even{true}, is_odd{false};
      for (; n--;)
      {
          std::swap(is_even, is_odd);
      }
      return is_even;
  }

I'm not going to argue this is good, but it's fairly analogous:

    boolean isEven(int n) {
        boolean even = true;
        for (; n > 0; --n) even = !even;
        return even;
    }

Your implementation has lost the encapsulation of mine, and broken the call-graph relationships. For example:

- Updates and bug-fixes to the `isOdd` function will not be inherited by your `isEven` function.

- If I set a breakpoint in this function, it won't get triggered when I call `isOdd`.

- Your `isEven` function requires an implementation of `!`

- etc.

> - Updates and bug-fixes to the `isOdd` function will not be inherited by your `isEven` function.

> - If I set a breakpoint in this function, it won't get triggered when I call `isOdd`.

    boolean isOdd(int n) {
      return !isEven(n);
    }

> - Your `isEven` function requires an implementation of `!`

Yes, but this language has one, so that's fine.

Many of the replies to this comment seem to have focused on the problem domain (numbers and booleans); and missed the main feature I was trying to show about recursion, which is a collection of functions delegating sub-tasks between themselves (rather than e.g. trampolining via a "main loop")

A closer analogy to my code would be something like this: the domain logic is still abstracted and encapsulated into separate units; the relationships between those units are preserved (e.g. if we set a breakpoint in `even_step`, it will be triggered by `odd`); etc. However, the loop here is literally just a trampoline for thunks, which makes it highly non-idiomatic for imperative/looping style:

  type STEP[T] = either[T, unit => STEP[T]]

  stepper[T](current: STEP[T]): T = {
    for (result = current; result.isRight(); result = result.value(unit))
    return result
  }

  even(n: uint): boolean = stepper(n match {
    case 0: left(true)
    case n: right(() => odd(n-1))
  })

  odd(n: uint): boolean = stepper(n match {
    case 0: left(false)
    case n: right(() => even(n-1))
  })

Instead, we could defunctionalise; but that requires some separate data structure and "interpreter":

  type STEP = ODD(n: uint) | EVEN(n: uint) | RETURN(x: boolean)

  even_impl(n: uint): STEP = n match {
    case 0: RETURN(true)
    case n: ODD(n-1)
  }

  odd_impl(n: uint): STEP = n match {
    case 0: RETURN(false)
    case n: EVEN(n-1)
  }

  interpret(current: STEP): boolean = {
    while (!current.isReturn) {
      current = current match {
        case ODD(n): odd_impl(n)
        case EVEN(n): even_impl(n)
      }
    }
    return current.x
  }

  odd(n: uint): boolean = interpret(ODD(n))

  even(n: uint): boolean = interpret(EVEN(n))

I think the underlying claim by the OP is that they don't really run into situations in practice that need this kind of mutual recursion. Certainly, mutual recursion is not at all necessary for this boolean example; you argue that the obvious imperative form is not a direct analogue, but it's not really clear in what situation a direct analogue is desirable in the first place.

> I think the underlying claim by the OP is that they don't really run into situations in practice that need this kind of mutual recursion

As mentioned in my comment, this is applicable wherever we have a "main loop". For example, a game might have a bunch of separate functions/methods to handle the various parts of the game; and a "main loop" which passes the return values of some as arguments to others:

  function main() {
    world = initWorld()
    while(true) {
      if (quitPressed()) break;

      delta = calculateVelocities(world)
      world = updatePositions(delta, world)
      collisions = findCollisions(world)
      world = handleEvents(mkEvents(collisions), world)
    }
    print("Goodbye")
    quit()
  }

Instead of passing data indirectly, by returning to the "main loop"; we could instead have those functions pass their results directly into whatever comes next. For example:

  function main() { gameStep(initWorld()) }

  function gameStep(world) {
    if (quitPressed()) quit(print("Goodbye"))
    else worldStep(world)
  }

  function worldStep(world) {
    delta = calculateVelocities(world)
    updatePositions(delta, world)
  }

  function updatePositions(delta, world) {
    newWorld = <existing logic>
    collisions = findCollisions(newWorld)
    handleEvents(mkEvents(collisions), newWorld)
  }

  function handleEvents(events, world) {
    newWorld = <existing logic>
    gameStep(newWorld)
  }

This is a lot more complicated than the even/odd example, but it's the same pattern. In this case, it's probably clear why we wouldn't want to in-line all of the calculations into one gigantic loop, mixing up physics simulation, collision detection, input handling, combat system, and whatever else this game does.

Again, not saying this is better/worse than a "main loop" (e.g. it can be helpful to have a "central location" to prevent spaghetti code); but (a) this style isn't possible without tail-call elimination, and (b) those who don't have tail-call elimination maybe wouldn't consider such an implementation.

> Again, not saying this is better/worse than a "main loop" (e.g. it can be helpful to have a "central location" to prevent spaghetti code); but (a) this style isn't possible without tail-call elimination, and (b) those who don't have tail-call elimination maybe wouldn't consider such an implementation.

Sure, this is an example where tail calls work as well as a central loop to solve the problem. But OP was looking specifically for a situation where recursion has an active "sustained advantage over looping", i.e., where the solution can be expressed far more naturally through recursion than through looping. Failing that, favoring recursion can just be boiled down to the peculiar preferences of the FP zeitgeist. (That is, even if the language does have tail-call elimination, that doesn't automatically make recursion the better solution.)

> In this case, it's probably clear why we wouldn't want to in-line all of the calculations into one gigantic loop, mixing up physics simulation, collision detection, input handling, combat system, and whatever else this game does.

I don't see what that has to do with loops vs. recursion. In real-world imperative code, we'd break up our main loop into calls to separate stages of the cycle, then break up each stage into calls to different encapsulated submodules, etc.; we wouldn't need to make the loop a 100k-line wall of code running every tiny step. (Compilers can do that part on their own.) Do you mean that this mutually-recursive style can assist with encapsulation in some particular way?

FWIW for my comment I essentially used your code and cleaned up compiler-generated imperative code.

So yes it used the fact that it only recursed to n-1 but did not use any optimizations related to booleans. And looking at other examples can see general principles. You store a data structure for each function which acts as a cache. For example, keeping to functions of ints, if you called foo(n - k) then instead of using one register for each function it would use a size k ring buffer.

Totally! Clojure is kind of great for this, the loop form in Clojure is really recursion as `loop` just provides a point(fn) for `recur` to return as well as a let binding. You could also just call `recur` in any fn. And, it has side-effect forms like do, doseq, dotimes, etc.

I'm glad you enjoyed the read though :)

> Nobody has yet convinced me that recursion has any sustained advantage over looping.

most sql systems support recursive queries. I believe recursive code can be analyzed by the system and executed in a the most efficient manner.

Loops have sideffects closely linking them to actual execution, which makes them blackboxes to the system.

If you're talking about recursive common table expressions, those are called recursive, but are really iterative. The PostgreSQL documentation describes the iterative evaluation:

https://www.postgresql.org/docs/current/queries-with.html#id...

Note how there is no way to remove a row from the result set once it has been added. That would not be the case with a truly recursive query, because you would be constructing a new result set at every step. As a concrete example, try to write a graph query which finds all nodes exactly three edges from some starting node. That would be trivial with true recursion, but is impossible with a recursive CTE alone.

>Nobody has yet convinced me that recursion has any sustained advantage over looping.

Recursion gives you a stack by default. You don't have to explicitly think about the stack. In looping the stack must be explicit.

Recursion and looping are the same thing. Recursion can be mechanically translated to a for loop and a stack, the concepts are isomorphic.

On paper perhaps, but I have yet to see a compiler that can take any arbitrary recursive subroutine and automatically optimize it into a Tail Call Optimized (that is, transform the recursive parts into goto/jumps similar to a loop) version. Non optimized recursion is not hard to understand, the problem is any performant recursive code needs to be manually rewritten as tail recursive which adds a lot of complexity. Built a better compiler and maybe more people would be willing to embrace functional programming.

It doesn't make any sense to convert any arbitrary recursion into tail called optimized.

If the recursion can be tail called optimized then yes the loop is the optimized performant implementation.

But if the recursion fundamentally utilizes the call stack then the reverse is actually true. The recursion is now the performant implementation of a for loop. So a loop conversion optimization actually doesn't make sense here. That's partly why a compiler won't optimize this.

Why? Because in recursion you utilize the call stack, in the for loop you're going to create a heap allocated stack and allocate on it repeatedly. Allocation slows down the iterations.

The only advantage of the for loop in this case is that there won't be stack overflow, but overall the recursive version will actually be faster.

I think the overflow may be part of the reason why the reverse conversion isn't done of taking heap allocated stacks and converting them into call stacks. The other issue is ownership of the heap allocated stacks, you can't convert it to a call stack if other entities own it or something else references it.

Works for O(log n) stack depth. In general, recursion is not viable.

This is quite false. Languages like Scheme (dialects), ML variants, Erlang and Haskell all make use of recursion in general and they produce very viable results.

> If the recursion can be tail called optimized then yes the loop is the optimized performant implementation.

Is it? My mental model of tail-call optimization is that it’s just a replacement of the stack variable values in place and a jump to the function entry point (which seems like the same amount of work as updating local variables in a loop and jumping to the head of the loop).

> The only advantage of the for loop in this case is that there won't be stack overflow, but overall the recursive version will actually be faster.

In languages, which have realized the value of recursion, a stack overflow does not happen. For example: https://docs.racket-lang.org/guide/Lists__Iteration__and_Rec...

Unless I'm mistaken, Erlang's compiler rewrites all recursion that explicitly returns a function call into tail-call, and eliminates all the stack in between

> all recursion that explicitly returns a function call

Yeah, but that's not "all recursion".

> On paper perhaps, but I have yet to see a compiler that can take any arbitrary recursive subroutine and automatically optimize it into a Tail Call Optimized (that is, transform the recursive parts into goto/jumps similar to a loop) version.

General recursion can be modelled coinductively via the "Delay" or "Partial" type, e.g. https://arxiv.org/abs/cs/0505037

Type-inference can figure out when recursive calls need to be wrapped in `Later`. We can then compile into a single `while` loop to unwrap the layers.

Had GPT-4 clarify some of the syntax for me https://poe.com/s/uj80au2i4TuNWgUa1pNm

That's pretty cool. Armed with the fundamentals outlined in the post, my intent was for the reader to infer how he or she can design a system in FP. I'm sorry if it wasn't clear enough in the code.

Recursion vs iteration reminds me of ordered sets vs hash tables.

Maybe partly because ordered sets are often implemented as trees, which are definitely easier to traverse recursively.

I find recursion nicer to work with mentally; continuous rather than discrete, with less edge cases to consider.

I used Scheme for a while so I like using recursion when loops get a bit hairy, but Guy Steele's talk on Parallel Programming* made me aware of the limitations of that way of working. Now that I've switched to Common Lisp I try to think about the algebraic properties of my functions so I can apply them using lparallel's preduce.

* https://www.infoq.com/presentations/Thinking-Parallel-Progra...

Looping, as in using a loop keyword, is synchronous. Recursion is also a loop, but can iterate asynchronously as necessary. That is the primary advantage.

Recursion doesn't do that by default, though. And if you have to alter your code to run recursive fns on a new thread or executor, nothing prevents you from doing something similar with a loop, either.

Recursion does do that by default respective to what the given function executes. No alteration or special convention is required. Loops that require use of syntax other than a function call are synchronous only.

If it would you can find me on IRC and I would be more than happy to show you how to program.

I see you've gone from recursion "can iterate asynchronously" to it "does do that by default".

In most languages, recursion is not asynchronous, even if it could be, which is part of the point I was making. I'm guessing English is not your first language.

I mostly agree, but one really nice use case for recursion is when dealing with trees. For example, writing a function parse_object() that recursively calls itself to parse child objects is way more pleasant than manually managing your own stack, especially if the tree has many kinds of objects and many branches.

Unfortunately in most languages this pattern will lead to stack overflow on medium-sized inputs, so you can't often use it unless you're using a language like Racket or Erlang which can't really stack overflow.