On Thu, Jul 16, 2015 at 3:28 AM, Robin Becker <ro...@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. -- https://mail.python.org/mailman/listinfo/python-list
