A new module for performing tail-call elimination

Robin Becker robin at reportlab.com
Fri Jul 17 10:57:54 CEST 2015


On 16/07/2015 17:17, Ian Kelly wrote:
> On Thu, Jul 16, 2015 at 3:28 AM, Robin Becker <robin at reportlab.com> wrote:
.............
>>
>> ....
>> 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.
>
that should have said "simple loops"


> 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.
>
I'm guessing, but is the implication that for loops can be specified finitely in 
advance, but while loops need some processing in the calculation to determine 
termination? I'm an engineer :(
-- 
Robin Becker



More information about the Python-list mailing list