A new module for performing tail-call elimination
ian.g.kelly at gmail.com
Thu Jul 16 18:17:09 CEST 2015
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
>> 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
>> 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
> 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.
More information about the Python-list