Hi everyone,
I'm working my way thorugh a book on computation (Minksy 1967) and am having a hard time with relating a recursive function to a function defined in terms of loops. Specifically he asks to find the relationship between two functions:
The Ackermann function (all code in python):
def a(n,m):
if n==0:
return m+1
if m==0:
return a(n-1,1)
return a(n-1,a(n,m-1))
And a function that computes with n nested loops:
def p(n,m):
for i_1 in range(m):
for i_2 in range(m):
...
for i_n in range(m):
m+=1
A recursive way of writing this (with one loop) is:
def p(n,m):
if n==0:
return m+1
for i in range(m):
m=p(n-1,m)
return m
Or a fully recursive way to write it would be:
def p(n,m):
return P(n,m,m)
def P(n,k,m):
if n==0:
return m+1
if k==1:
return P(n-1,m,m)
m=P(n,k-1,m)
return P(n-1,m,m)
Is there some simple way these two functions are related? I feel like I'm crawling around in a fog - any insight you could give me into how to approach these sorts of problems would be greatly appreciated. Also, is there a way to implement the fully recursive loop function without the introduction of a third parameter? Thanks.