Comment prédire la profondeur d'appel maximale d'une méthode récursive ?

Question

Afin d'estimer la profondeur d'appel maximale qu'une méthode récursive peut atteindre avec une quantité de mémoire donnée, quelle est la formule (approximative) permettant de calculer la mémoire utilisée avant qu'une erreur de débordement de pile soit susceptible de se produire ?

Editar:

Beaucoup ont répondu par "ça dépend", ce qui est raisonnable. Supprimons donc certaines des variables en utilisant un exemple trivial mais concret :

public static int sumOneToN(int n) {
    return n < 2 ? 1 : n + sumOneToN(n - 1);
}

Il est facile de montrer que l'exécution de cette opération dans mon IDE Eclipse explose pour n un peu moins de 1000 (ce qui me paraît étonnamment bas). Cette limite de profondeur d'appel aurait-elle pu être estimée sans l'exécuter ?

Edit : Je ne peux m'empêcher de penser qu'Eclipse a une profondeur d'appel maximale fixe de 1000, car je suis arrivé à 998 mais il y en a un pour la méthode principale et un pour l'appel initial à la méthode, ce qui fait que 1000 en tout. Ce chiffre est trop rond pour être une coïncidence. Je vais poursuivre mes recherches. J'ai juste Dux overhead le paramètre -Xss vm ; c'est la taille maximale de la pile, donc le runner Eclipse doit avoir -Xss1000 placer quelque part

Answer 1

Ceci est clairement spécifique à la JVM et peut-être aussi à l'architecture.

J'ai mesuré les éléments suivants :

  static int i = 0;
  public static void rec0() {
      i++;
      rec0();
  }

  public static void main(String[] args) {
      ...
      try {
          i = 0; rec0();
      } catch (StackOverflowError e) {
          System.out.println(i);
      }
      ...
  }

en utilisant

Java(TM) SE Runtime Environment (build 1.7.0_09-b05)
Java HotSpot(TM) 64-Bit Server VM (build 23.5-b02, mixed mode)

fonctionnant sur x86.

Avec une pile Java de 20 Mo ( -Xss20m ), le coût amorti fluctuait autour de 16-17 octets par appel. Le plus bas que j'ai vu était de 16,15 octets/trame. J'en conclus donc que le coût est de 16 octets et que le reste est constitué d'autres frais généraux (fixes).

Une fonction qui prend un seul int a fondamentalement le même coût, 16 octets/trame.

Il est intéressant de noter qu'une fonction qui prend dix ints nécessite 32 octets/trame. Je ne sais pas pourquoi le coût est si faible.

Les résultats ci-dessus s'appliquent après que le code a été compilé en JAT. Avant la compilation, le coût par trame est de beaucoup, beaucoup plus élevé. Je n'ai pas encore trouvé un moyen de l'estimer de manière fiable. Cependant, cela signifie que vous n'avez aucun espoir de prédire de manière fiable la profondeur maximale de récursion jusqu'à ce que vous puissiez prédire de manière fiable si la fonction récursive a été compilée en JAT.

Tout cela a été testé avec un ulimit des tailles de pile de 128K et 8MB. Les résultats sont les mêmes dans les deux cas.

Answer 2

Réponse partielle seulement : de JVM Spec 7, 2.5.2 Les cadres de pile peuvent être alloués sur le tas, et la taille de la pile peut être dynamique. Je ne pourrais pas le dire avec certitude, mais il semble qu'il devrait être possible d'avoir une taille de pile limitée uniquement par la taille du tas :

Étant donné que la pile de la machine virtuelle Java n'est jamais manipulée directement, sauf pour pousser et extraire des cadres, les cadres peuvent être alloués au tas.

y

Cette spécification permet aux piles de machines virtuelles Java d'avoir une taille fixe ou de s'étendre et se contracter dynamiquement selon les besoins. une taille fixe ou de s'étendre et se contracter dynamiquement selon les besoins du calcul. Si les piles de la machine virtuelle Java sont de taille fixe, la taille de chaque pile de machine virtuelle Java peut être choisie indépendamment lors de la création de cette pile.

Une mise en œuvre de la machine virtuelle Java peut permettre au programmeur ou à l'utilisateur de contrôler la taille initiale des piles de la machine virtuelle Java. l'utilisateur le contrôle de la taille initiale des piles de la machine virtuelle Java, ainsi que, dans le cas d'une expansion ou d'une contraction dynamique des piles de machines virtuelles le contrôle des tailles maximale et minimale.

Cela dépendra donc de l'implémentation de la JVM.

Answer 3

Complément à la réponse de NPE :

La profondeur maximale de la pile semble être flexible . Le programme de test suivant imprime largement différents numéros :

public class StackDepthTest {
    static int i = 0;

    public static void main(String[] args) throws Throwable {
        for(int i=0; i<10; ++i){
            testInstance();
        }
    }

    public static void testInstance() {
        StackDepthTest sdt = new StackDepthTest();
        try {
            i=0;
            sdt.instanceCall();
        } catch(StackOverflowError e){}
        System.out.println(i);
    }

    public void instanceCall(){
        ++i;
        instanceCall();
    }
}

La sortie est :

10825
10825
59538
59538
59538
59538
59538
59538
59538
59538

J'ai utilisé la version par défaut de ce JRE :

java version "1.7.0_09"
OpenJDK Runtime Environment (IcedTea7 2.3.3) (7u9-2.3.3-0ubuntu1~12.04.1)
OpenJDK 64-Bit Server VM (build 23.2-b09, mixed mode)

La conclusion est donc la suivante : si vous en avez assez (c'est-à-dire plus de deux fois), vous avez une seconde chance ;-)

Answer 4

La réponse est : tout dépend.

Tout d'abord, la taille de la pile Java peut être modifiée.

Ensuite, la taille du cadre de pile d'une méthode donnée peut varier en fonction de différentes variables. Vous pouvez consulter la section Taille du cadre de la pile des appels de Pile d'appels - Wikipédia pour plus de détails.

Answer 5

Dépend de l'architecture de votre système (adresses 32 ou 64 bits), du nombre de variables locales et des paramètres de la méthode. Si c'est tail-recursive pas de surcharge, si le compilateur l'optimise en boucle.

Vous voyez, pas de réponse simple.