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.