Java LanguageRécursivité


Introduction

La récursivité se produit lorsqu'une méthode s'appelle elle-même. Une telle méthode est appelée récursive . Une méthode récursive peut être plus concise qu'une approche non récursive équivalente. Cependant, pour une récursivité profonde, une solution itérative peut parfois consommer moins d'espace de pile fini d'un thread.

Cette rubrique comprend des exemples de récursivité en Java.

Remarques

Concevoir une méthode récursive

Lorsque vous concevez une méthode récursive, gardez à l'esprit que vous avez besoin de:

  • Cas de base. Cela définira quand votre récursivité s'arrêtera et affichera le résultat. Le cas de base dans l'exemple factoriel est:

    if (n <= 1) {
        return 1;
    }
    
  • Appel récursif. Dans cette instruction, vous appelez à nouveau la méthode avec un paramètre modifié. L'appel récursif dans l'exemple factoriel ci-dessus est:

    else {
        return n * factorial(n - 1);
    }
    

Sortie

Dans cet exemple, vous calculez le n-ième nombre factoriel. Les premières factorielles sont:

0! = 1

1! = 1

2! = 1 x 2 = 2

3! = 1 x 2 x 3 = 6

4! = 1 x 2 x 3 x 4 = 24

...


Élimination Java et Tail-Call

Les compilateurs Java actuels (jusqu’à Java 9 inclus) n’effectuent pas l’élimination des appels de queue. Cela peut avoir un impact sur les performances des algorithmes récursifs, et si la récursivité est suffisamment profonde, cela peut conduire à des StackOverflowError de StackOverflowError ; voir Récursivité profonde est problématique en Java

Récursivité Exemples Liés