Il est possible de calculer la fonction ackermann récursive (m, n) avec les arguments m> = 4 et n> = 1 en python sans dépasser la profondeur de récursion maximale?

Question

Il est possible de calculer la fonction récursive totale calculable ackermann(m,n) avec les arguments m>=4 et n>=1 en python sans dépasser la profondeur maximale de récursivité?

def ackermann(m,n): 

    if m == 0: 
     return n+1 
    if n == 0: 
     return ackermann(m-1,1) 
    else: 
     return ackermann(m-1,ackermann(m,n-1)) 

ackermann(4,1) 

Answer 1

Pour ce niveau de réponse, utilisez la programmation dynamique: memoize la fonction. Cela signifie que vous gardez une table des résultats précédents. Si vous trouvez un résultat qui a déjà été calculé, vous le retournez de la table. Seulement quand c'est un nouvel appel, faites-vous le calcul - et dans ce cas, la plupart ou la totalité des appels récursifs seront dans la table. Par exemple:

import sys 
sys.setrecursionlimit(30000) 

memo = {} 

def ack(m, n): 
    if not (m, n) in memo: 
     result = (n + 1) if m == 0 else (
      ack(m-1, 1) if n == 0 else ack(m-1, ack(m, n-1))) 
     memo[(m, n)] = result 
    return memo[(m, n)] 

print ack(3, 4) 
print ack(4, 1) 
print ack(4, 2) 

Vous aurez toujours des problèmes avec quoi que ce soit aussi grand que ack (4, 2), en raison de l'utilisation de la mémoire.

125 
65533 
Segmentation fault (core dumped) 

Answer 2

Oui. On peut utiliser sys.setrecursionlimit et plus de mathématiques pour améliorer l'algorithme. Voir le Rosetta Code task pour le code Python.

Remarque!

Je viens de re-couru ack2:

%timeit a2 = ack2(4,2) 
1000 loops, best of 3: 214 µs per loop 

len(str(a2)) 
Out[9]: 19729 

soit près de vingt chiffres dans la réponse.