La fonction Ackermann et la récursion

Question

J'ai essayé d'écrire la fonction récursive Ackermann en Java. Mais je pense que je suis allé très très mal quelque part! Quelqu'un pourrait-il jeter un coup d'oeil, vérifier et peut-être pointer mon dans la bonne direction de corriger mon code? Merci!

La question que j'ai avec le code est que, après je l'ai écrit, je pensais que, si n == 0 et m == 0, il n'y a pas un espace pour cela? Est-ce que cela tomberait sous le if (m == 0) ou aurait-il besoin de sa propre if-statement?

Ma solution suivante est-elle correcte? Si je lui donne les mêmes nombres dans une séquence différente, cela donne un résultat différent et je ne suis pas sûr que cela soit le cas. J'y ai réfléchi encore un peu et je pense que je me suis encore plus trompé. Si vous ne pouvez pas comprendre ce que j'ai fait, j'ai donné à chaque instruction if un sens opposé, parce que je pensais que si les valeurs m et n sont données différemment, le code suivant fonctionnera. Ce n'est clairement pas le cas, mais quelqu'un pourrait-il essayer d'expliquer où je me suis trompé?

public static int ackermann(int m, int n) { 

     if (m == 0) { 

      return n + 1; 

     } else if (n == 0) { 

      return m + 1; 

     } else if ((m > 0) && (n == 0)) { 

      return ackermann(m-1, n); 

     } else if ((n > 0) && (m == 0)) { 

      return ackermann(n-1, m); 

     } else if ((m > 0) && (n > 0)) { 

      return ackermann(m-1, ackermann(m,n-1)); 

     } else if ((n > 0) && (m > 0)) { 

      return ackermann(n-1, ackermann(n, m-1)); 

     } else { 

      return 0; 

     } 

    } 

Answer 1

Je pense que votre première version est presque correcte. Je modifie légèrement:

public static int ackermann(int m, int n) { 
    if (m < 0 || n < 0) { 
     throw new IllegalArgumentException("Non-negative args only!"); 
    } 

    if (m == 0) { 
     return n + 1; 
    } else if (n == 0) { 
     return ackermann(m-1, 1); // Corrected! 
    } else { 
     // perforce (m > 0) && (n > 0) 
     return ackermann(m-1, ackermann(m,n-1)); 
    } 
} 

Le m == 0 && n == 0 cas doit être inclus dans le m == 0 cas.

EDIT: Notez que le Ackermann function est défini uniquement pour les arguments non négatifs. En particulier, ackermann(0, -1) devrait lancer une exception. Ainsi, vous ne pouvez pas convertir votre dernière clause else en throw.

Answer 2

Le 'si m = 0' règle vaut pour toutes les valeurs de n, donc A (0, 0) est 1.

La clause else ne pouvait être utilisée que si m et n étaient les deux négatifs à l'entrée de la fonction, qui pourraient être diagnostiqués comme une exception. En effet, si m ou n est négatif, vous devriez diagnostiquer l'erreur. Alternativement, puisque A (m, n) ne renvoie jamais le zéro autrement, le 0 pourrait être considéré comme signalant l'erreur.

Notez que la profondeur de pile requise pour évaluer A (m, n) est la même que la réponse - et A (m, n) devient très grande très rapidement. Ne vous embêtez pas à essayer d'évaluer A (4, 4); votre ordinateur n'a pas assez de mémoire.

Answer 3

Cette partie est erroné:

} else if ((m > 0) && (n == 0)) { 
     return ackermann(m-1, n); 

Cela devrait être A (m - 1, 1)

Answer 4

Le premier extrait est OK, sauf qu'il retourne ackermann(m-1, n) au lieu de ackermann(m-1, 1) dans le second cas . Le cas par défaut, qui ne devrait jamais arriver, devrait lancer un IllegalStateException au cas où cela se produirait.

Answer 5

Il est intéressant de noter que toutes les réponses à votre question précise votre erreur dans la première version, mais ne dit rien sur la grande erreur deuxième version

else if (n == 0) { 
     return m + 1; 
    } 

qui, pour des nombres entiers positifs, est équivalent en bon état avec

else if ((m > 0) && (n == 0)) { 
     return ackermann(m-1, n); 
    } 

Ainsi, votre fonction sera de retour m + 1 mais pas ACKERMANN (m-1, 1) qui devrait le second cas ((m> 0) & & (n == 0)).