title: Ackermann function versus n nested loops
body: <p>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:</p>
  
  <p>The Ackermann function (all code in python):</p>
  
  <pre><code>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))
  </code></pre>
  
  <p>And a function that computes with n nested loops:</p>
  
  <pre><code>def p(n,m):
      for i_1 in range(m):
          for i_2 in range(m):
             ...
               for i_n in range(m):
                    m+=1
  </code></pre>
  
  <p>A recursive way of writing this (with one loop) is:</p>
  
  <pre><code>def p(n,m):
       if n==0:
           return m+1
       for i in range(m):
           m=p(n-1,m)
       return m
  </code></pre>
  
  <p>Or a fully recursive way to write it would be:</p>
  
  <pre><code>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) 
  </code></pre>
  
  <p>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.</p>