Java Language
Récursivité

Introduction

Remarques

L'idée de base de la récursivité

Qu'est-ce que la récursivité:

En général, la récursivité se produit lorsqu'une fonction s'appelle directement ou indirectement. Par exemple:

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

Conditions d'application de la récursivité à un problème:

Il existe deux conditions préalables à l’utilisation de fonctions récursives pour résoudre un problème spécifique:

1. Il doit y avoir une condition de base pour le problème, qui sera le point final de la récursivité. Lorsqu'une fonction récursive atteint la condition de base, il ne fait plus aucun appel récursif (plus profond).

2. Chaque niveau de récursivité devrait tenter un petit problème. La fonction récursive divise donc le problème en parties plus petites et plus petites. En supposant que le problème soit fini, cela garantira la fin de la récursivité.

À Java, il existe une troisième condition préalable: il ne faut pas avoir à se recentrer trop profondément pour résoudre le problème; voir Récursivité profonde est problématique en Java

Exemple

La fonction suivante calcule les factorielles en utilisant la récursivité. Notez que la méthode factorial s'appelle elle-même dans la fonction. Chaque fois qu'il appelle lui-même, il réduit le paramètre n de 1. Lorsque n atteint 1 (la condition de base), la fonction ne se déclenche plus.

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

^{Ce n'est pas un moyen pratique de calculer les factorielles en Java, car il ne prend pas en compte le débordement d'entier, ou le débordement de pile d'appel (c'est-à- StackOverflowError exceptions StackOverflowError ) pour les grandes valeurs de n .}

Calcul du nombre N ° Fibonacci

La méthode suivante calcule le Nième nombre de Fibonacci en utilisant la récursivité.

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

La méthode implémente un cas de base (n <= 2) et un cas récursif (n> 2). Ceci illustre l'utilisation de la récursivité pour calculer une relation récursive.

Cependant, bien que cet exemple soit illustratif, il est également inefficace: chaque instance de la méthode appelle la fonction elle-même deux fois, ce qui entraîne une croissance exponentielle du nombre de fois que la fonction est appelée lorsque N augmente. La fonction ci-dessus est O (2 ^N ), mais une solution itérative équivalente a la complexité O (N). En outre, il existe une expression "forme fermée" qui peut être évaluée en multiplications à virgule flottante O (N).

Calculer la somme des entiers de 1 à N

La méthode suivante calcule la somme des entiers de 0 à N en utilisant la récursivité.

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

Cette méthode est O (N) et peut être réduite à une simple boucle en utilisant l’optimisation de l’appel. En fait, il existe une expression de forme fermée qui calcule la somme dans les opérations O(1) .

Calcul de la puissance N du nombre

La méthode suivante calcule la valeur de num élevée à la puissance de exp utilisant la récursivité:

public long power(final int num, final int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return num;
    }
    return num * power(num, exp - 1);
}

Ceci illustre les principes mentionnés ci-dessus: la méthode récursive implémente un cas de base (deux cas, n = 0 et n = 1) qui termine la récursivité et un cas récursif qui appelle à nouveau la méthode. Cette méthode est O (N) et peut être réduite à une simple boucle en utilisant l’optimisation de l’appel.

Inverser une chaîne en utilisant la récursivité

Voici un code récursif pour inverser une chaîne

/**
 * Just a snippet to explain the idea of recursion
 *
 **/

public class Reverse {
    public static void main (String args[]) {
        String string = "hello world";
        System.out.println(reverse(string)); //prints dlrow olleh
    }

    public static String reverse(String s) {
        if (s.length() == 1) {
            return s;
        }
    
        return reverse(s.substring(1)) + s.charAt(0);
    }
}

Traverser une structure de données Tree avec récursivité

Considérons la classe Node ayant 3 données membres, le pointeur enfant gauche et le pointeur enfant droit comme ci-dessous.

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

Nous pouvons parcourir l'arbre construit en connectant plusieurs objets de la classe Node comme ci-dessous, la traversée est appelée traversée d'ordre de l'arbre.

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

Comme démontré ci-dessus, en utilisant la récursivité, nous pouvons traverser la structure de données de l'arborescence sans utiliser aucune autre structure de données qui n'est pas possible avec l'approche itérative .

Types de récursivité

La récursivité peut être classée comme récursion de tête ou récursivité de queue , selon l'endroit où l'appel de méthode récursif est placé.

Dans la récursion principale , l'appel récursif, lorsqu'il se produit, intervient avant tout autre traitement dans la fonction (pensez à ce qu'il se passe en haut ou en bas de la fonction).

Dans la récursion de la queue , c'est le contraire: le traitement a lieu avant l'appel récursif. Choisir entre les deux styles récursifs peut sembler arbitraire, mais le choix peut faire toute la différence.

Une fonction avec un chemin avec un seul appel récursif au début du chemin utilise ce qu'on appelle la récursion de la tête. La fonction factorielle d'une exposition précédente utilise la récursion de la tête. La première chose qu'il fait une fois qu'il détermine que la récursivité est nécessaire est de s'appeler avec le paramètre décrémenté. Une fonction avec un seul appel récursif à la fin d'un chemin utilise la récursion de queue.

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

Si l'appel récursif se produit à la fin d'une méthode, cela s'appelle une tail recursion . La récursion de la queue est similar to a loop . La method executes all the statements before jumping into the next recursive call .

Si l'appel récursif se produit au beginning of a method, it is called a head recursion . La method saves the state before jumping into the next recursive call .

Référence: La différence entre la récursion tête et queue

StackOverflowError & récursivité en boucle

Si un appel récursif devient "trop ​​profond", cela se traduit par une StackOverflowError . Java alloue une nouvelle image pour chaque appel de méthode sur la pile de son thread. Cependant, l'espace de la pile de chaque thread est limité. Trop de cadres sur la pile mènent au dépassement de pile (SO).

Exemple

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

L'appel de cette méthode avec des paramètres importants (par exemple, la recursion(50000) entraînera probablement un débordement de pile. La valeur exacte dépend de la taille de la pile de threads, qui dépend à son tour de la structure du thread, des paramètres de ligne de commande tels que -Xss ou taille par défaut pour la JVM.

solution de contournement

Une récursivité peut être convertie en une boucle en stockant les données pour chaque appel récursif dans une structure de données. Cette structure de données peut être stockée sur le tas plutôt que sur la pile de threads.

En général, les données requises pour restaurer l'état d'une invocation de méthode peuvent être stockées dans une pile et une boucle while peut être utilisée pour "simuler" les appels récursifs. Les données pouvant être requises incluent:

• l'objet pour lequel la méthode a été appelée (méthodes d'instance uniquement)
• les paramètres de la méthode
• variables locales
• la position actuelle dans l'exécution ou la méthode

Exemple

La classe suivante permet de récurer une arborescence jusqu'à une profondeur spécifiée.

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this(data, null, null);
    }

    public Node(int data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void print(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (left != null) {
                left.print(maxDepth-1);
            }
            System.out.print(data);
            if (right != null) {
                right.print(maxDepth-1);
            }
            System.out.print(")");
        }
    }

}

par exemple

Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();

Des tirages

(((...)20(...))10((...)30))

Cela pourrait être converti à la boucle suivante:

public class Frame {

    public final Node node;

    // 0: before printing anything
    // 1: before printing data
    // 2: before printing ")"
    public int state = 0;
    public final int maxDepth;

    public Frame(Node node, int maxDepth) {
        this.node = node;
        this.maxDepth = maxDepth;
    }

}

List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call

while (!stack.isEmpty()) {
    // get topmost stack element
    int index = stack.size() - 1;
    Frame frame = stack.get(index); // get topmost frame
    if (frame.maxDepth <= 0) {
        // termial case (too deep)
        System.out.print("(...)");
        stack.remove(index); // drop frame
    } else {
        switch (frame.state) {
            case 0:
                frame.state++;

                // do everything done before the first recursive call
                System.out.print("(");
                if (frame.node.left != null) {
                    // add new frame (recursive call to left and stop)
                    stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
                    break;
                }
            case 1:
                frame.state++;

                // do everything done before the second recursive call
                System.out.print(frame.node.data);
                if (frame.node.right != null) {
                    // add new frame (recursive call to right and stop)
                    stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
                    break;
                }
            case 2:
                // do everything after the second recursive call & drop frame
                System.out.print(")");
                stack.remove(index);
        }
    }
}
System.out.println();

Note: Ceci est juste un exemple de l'approche générale. Souvent, vous pouvez trouver une meilleure façon de représenter un cadre et / ou de stocker les données du cadre.

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

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.