Funzione Ackermann contro n loop nested

Question

Sto lavorando a un mio libro sul calcolo (Minksy 1967) e sto attraversando un periodo difficile nel mettere in relazione una funzione ricorsiva con una funzione definita in termini di cicli. Specificamente chiede di trovare la relazione tra due funzioni:

La funzione Ackermann (tutto il codice in pitone):

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)) 

e una funzione che calcola con n cicli annidati:

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 modo ricorsivo di scrivere questo (con un anello) è:

def p(n,m): 
    if n==0: 
     return m+1 
    for i in range(m): 
     m=p(n-1,m) 
    return m 

O una completamente ricorre Il modo migliore per scrivere sarebbe:

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) 

C'è un modo semplice in cui queste due funzioni sono correlate? Mi sento come se stessi gattonando in una nebbia - qualsiasi intuizione che potresti darmi su come affrontare questo tipo di problemi sarebbe molto apprezzata. Inoltre, c'è un modo per implementare la funzione del ciclo completamente ricorsivo senza l'introduzione di un terzo parametro? Grazie.

Answer 1

Uhm ... Non penso che questo ti aiuterà molto, anche io sono un po 'sconcertato, ma ecco i miei pensieri.

• Ackerman (0, m) == p (0, m)
• Ackerman (1, m + 1) == p (1, m)

modifica - Aspetto I penso di aver sbagliato la funzione. Darò questo più pensiero dopo, e se penso a qualcosa aggiorno!