Java Language La récursivité profonde est problématique en Java


Exemple

Considérons la méthode naïve suivante pour ajouter deux nombres positifs en utilisant la récursivité:

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

Ceci est algorithmiquement correct, mais il a un problème majeur. Si vous appelez add avec un grand a , il se bloquera avec une StackOverflowError , sur n'importe quelle version de Java jusqu'à (au moins) Java 9.

Dans un langage de programmation fonctionnel typique (et dans de nombreux autres langages), le compilateur optimise la récursion de la queue . Le compilateur remarquerait que l'appel à add (à la ligne balisée) est un appel de queue , et réécrirait effectivement la récursivité en tant que boucle. Cette transformation s'appelle l'élimination par appel de queue.

Cependant, les compilateurs Java de la génération actuelle n'effectuent pas l'élimination des appels de queue. (Ce n'est pas un simple oubli. Il y a des raisons techniques substantielles à cela: voir ci-dessous.) Au lieu de cela, chaque appel récursif de add provoque l'allocation d'une nouvelle trame sur la pile du thread. Par exemple, si vous appelez add(1000, 1) , il faudra 1000 appels récursifs pour arriver à la réponse 1001 .

Le problème est que la taille de la pile de threads Java est fixe lorsque le thread est créé. (Cela inclut le thread "principal" dans un programme à thread unique.) Si trop de cadres de pile sont alloués, la pile débordera. La JVM détectera ceci et StackOverflowError une StackOverflowError .

Une approche pour gérer cela consiste simplement à utiliser une plus grande pile. Certaines options JVM contrôlent la taille par défaut d'une pile et vous pouvez également spécifier la taille de la pile en tant que paramètre du constructeur Thread . Malheureusement, cela ne fait que "retarder" le débordement de la pile. Si vous devez faire un calcul qui nécessite une pile encore plus grande, StackOverflowError revient.

La vraie solution consiste à identifier les algorithmes récursifs dans lesquels une récursivité profonde est probable, et à effectuer manuellement l’optimisation des appels de queue au niveau du code source. Par exemple, notre méthode d' add peut être réécrite comme suit:

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

(De toute évidence, il existe de meilleures façons d’ajouter deux entiers. Ce qui précède sert simplement à illustrer l’effet de l’élimination manuelle de l’appel de la queue.)

Pourquoi l'élimination des appels de queue n'est pas encore implémentée en Java

Il y a un certain nombre de raisons pour lesquelles il n'est pas facile d'ajouter l'élimination des appels de queue à Java. Par exemple:

  • Certains codes peuvent s'appuyer sur StackOverflowError pour (par exemple) placer une limite sur la taille d'un problème de calcul.
  • Les responsables de la sécurité Sandbox s'appuient souvent sur l'analyse de la pile d'appels lorsqu'ils décident d'autoriser ou non le code non privilégié à effectuer une action privilégiée.

Comme l'explique John Rose dans "Tail calls in the VM" :

"Les effets de la suppression du cadre de pile de l'appelant sont visibles pour certaines API, notamment les contrôles de contrôle d'accès et le suivi de pile. C'est comme si l'appelant de l'appelant avait directement appelé l'appelé. Tous les privilèges Cependant, le couplage et l’accessibilité de la méthode appelée sont calculés avant le transfert du contrôle et prennent en compte l’appel appelant.

En d’autres termes, l’élimination de l’appel de bout en bout pourrait amener une méthode de contrôle d’accès à penser à tort qu’une API sensible à la sécurité était appelée par du code de confiance.