Apprentissage Java Recursion, fonction Ackerman

Question

Je travaille sur une fonction récursive Ackermann en Java. Je reçois une erreur à la ligne récursive peut, 23.

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

Merci beaucoup si quelqu'un pouvait indiquer ce qui est faux.

-Kyle

/*enter code here 

    Ackerman's function, A(m, n) is defined: 
    A(0 , n) = n + 1 for n >= 0 
    A(m , 0) = A(m – 1 , 1) for m > 0 
    A(m , n) = A(m – 1 , A(m , n - 1)) for n >= 0 

    */ 

    public class AckFun { 

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

     if (m == 0) { 
     return 2 * n; 
     } else if (m >= 1) { 
     if (n == 0) { 
     return 0; 
     } else if (n == 1) { 
     return 2; 
     } else { 
     return Ack(m - 1, Ack(m, n - 1)); 
     } 
     } 
     return n; // Not sure what to return here, Eclipse suggested this. 
    } 

    public static void main(String args[]) { 
     System.out.println(Ack(3, 4)); 
    } 
    } 

Answer 1

Vous devez rendre votre pile plus:

http://thilinamb.wordpress.com/2008/12/22/how-to-increase-the-java-stack-size/

Avec pile plus grand, il fonctionne sans stackoverflow, mais donne 0.

EDIT: Votre code est erroné, c'est pourquoi il donne la Erreur. Essayez de réécrire le code exactement comme le dit la définition:

//I assume that you check that n and m are non-negative before you run this 
    if (m == 0) { 
     return n + 1; 
    } else if (n == 0) { 
     return Ack(m - 1, 1); 
    } else { 
     return Ack(m - 1, Ack(m, n - 1)); 
    } 

PS. Ne me blâmez pas d'avoir posté du code source pour des problèmes de devoirs. Je crois que la meilleure façon d'apprendre la programmation est de lire et de comprendre le code de quelqu'un d'autre.

Answer 2

Vous avez dépassé la profondeur de récursivité maximale. C'est l'une des caractéristiques de la fonction Ackermann. :)

Si vous l'appelez avec des nombres plus petits, comme Ack(3,3), la pile ne déborde pas.

Il est possible d'augmenter la limite de profondeur de récursivité de Java, mais ce n'est pas forcément une bonne solution. Cela peut être un exercice de transformation du programme afin qu'il n'utilise pas la pile d'appels intégrée de Java, mais garde la trace de chaque appel dans une structure de données (peut-être une pile). Vous pouvez également utiliser memoization, où vous enregistrez le résultat de l'appel de fonction afin de ne pas avoir à calculer le même résultat encore et encore.

Answer 3

Avec un retour en face, vous n'avez pas besoin d'autre chose.

if (m == 0) return n + 1; 
if (n == 0) return ack (m - 1, 1); 
return ack (m - 1, ack (m, n - 1));