Earlier quoted context omitted.
>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. Bu…
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.