A new module for performing tail-call elimination

[Ian Kelly]

On Thu, Jul 16, 2015 at 3:28 AM, Robin Becker <robin at reportlab.com> wrote:
> ..........
>>
>>
>> The point is, people keep insisting that there are a vast number of
>> algorithms which are best expressed using recursion and which require TCO
>> to
>> be practical, and yet when asked for examples they either can't give any
>> examples at all, or they give examples that are not well-suited to
>> recursion. Or, at best, examples which are equally good when written
>> either
>> using recursion or iteration.
>>
>> I do believe that such examples surely must exist. But I'm yet to see one.
>
> ....
> I believe the classic answer is Ackermann's function
>
> http://demonstrations.wolfram.com/RecursionInTheAckermannFunction/
>
> which is said to be not "primitive recursive" ie cannot be unwound into
> loops; not sure whether that implies it has to be recursively defined or can
> perhaps be broken down some other way.

My recollection -- and it's been awhile since I've studied
computability theory so I may be distorting things here -- is that
primitive recursive functions can be computed using for loops, i.e.
loops where the number of iterations is bounded in advance, whereas
non-primitive recursive functions require while loops.