Récursivité en Java

Pour comprendre ce qu'est la récursivité, vous devez comprendre ce qu'est la récursivité. En fait, il n’y a rien de difficile à comprendre de telles fonctions, il suffit de bien les comprendre une fois. Et entraînez-vous en matière de programmation. Récursion en Java - 1

La récursivité se produit non seulement dans la programmation, mais aussi dans la vie réelle. Prenez un miroir dans vos mains et placez-vous devant un autre miroir. Le reflet du reflet se reflétera dans le reflet et ainsi de suite. Vous verrez un nombre infini de reflets aller vers l'infini. Vous pouvez en savoir plus sur la « vraie » récursivité dans l'article « Dédié au jour de la marmotte... » Revenons du monde réel au quotidien d'un programmeur. Définition simple : les fonctions récursives en Java sont des fonctions qui s'appellent elles-mêmes. Laissez-moi vous donner un exemple très simple et très nuisible :

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

Pourquoi est-ce nocif ? Je vous suggère de vérifier vous-même ! Si vous décidez de vous lancer dans cette aventure (et vous le ferez très probablement, programmeur !), écrivez dans les commentaires quelle erreur la JVM générera =) Cet exemple, et bien d'autres, démontrent que l'utilisation de la récursivité en Java doit être abordée avec prudence. . Vous devez comprendre où, quand et pourquoi une telle approche pour résoudre un problème est justifiée et vous assurer que votre fonction ne transforme pas l'exécution du programme en « Jour de la marmotte ». Il existe deux définitions plus importantes pour comprendre la récursivité :

Base de récursion - la condition de sortie du bloc d'appels récursifs - la solution de base au problème, dans des conditions où il n'est pas nécessaire d'appeler la récursivité.
L'étape de récursion se produit lorsqu'une fonction s'appelle elle-même lors de la modification de paramètres.

Un exemple classique d’utilisation d’une fonction récursive consiste à calculer la factorielle d’un nombre. Au cas où vous l'auriez oublié, permettez-moi de vous le rappeler : la factorielle d'un entier positif N(noté N !) est le produit de nombres de 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. À propos, la factorielle de zéro par définition est égale à 1. Ainsi, la factorielle peut être trouvée pour tout entier positif et zéro (dans le langage mathématique - pour l'ensemble des entiers non négatifs ou pour l'ensemble des nombres naturels et zéro). Je pense que vous comprenez que vous pouvez programmer des factorielles à l'aide de boucles. En fait, voici une méthode non récursive pour résoudre ce problème :

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Ajoutons une vérification que le nombre est positif et entier, et une vérification distincte pour zéro.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Je vais maintenant donner le code de la méthode pour résoudre ce problème de manière récursive :

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

Examinons les résultats de sortie des appels :

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

On obtient les valeurs attendues :

Ajoutons une belle sortie et calculons la factorielle pour un plus grand nombre :

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

On obtient : 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Dans ce cas, l’utilisation d’une fonction récursive est justifiée et sûre. Nous avons clairement défini la condition de sortie du bloc récursif, et nous sommes convaincus qu'elle est réalisable : on saisit un nombre entier non négatif, si le nombre est égal à zéro ou à un, on renvoie le résultat, si le nombre est supérieur , on multiplie le résultat par une fonction du nombre n-1. En utilisant la factorielle de trois comme exemple :

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

Concernant la prudence à l'usage : quelle est la vulnérabilité de cette fonction ? Si vous donnez à une méthode un nombre négatif comme paramètre, alors la vérification

if (n == 1 || n == 0) {
    return result;
}

cela n’a aucun sens et nous nous retrouverons dans un cycle sans fin d’appels à nous-mêmes. Il vaut la peine d'ajouter un contrôle de non-négativité :

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

Et tout ira bien.

Quel est l’avantage d’une méthode par rapport à une autre ? Il ne semble pas y avoir une grande différence, mais en fait, de nombreux appels récursifs auront un impact négatif sur les performances et la consommation de mémoire : la pile d'appels est une ressource presque incontrôlable et dans des conditions différentes pour appeler la même fonction récursive, nous pouvons ou non avoir des problèmes associés à cette ressource. Presque tous les problèmes résolus à l'aide d'itérations (cycles comme for-each) peuvent également être résolus de manière récursive. L'avantage de la récursivité est la lisibilité et la facilité d'écriture ; nous avons évoqué les inconvénients plus haut : la possibilité de se « tirer une balle dans le pied » n'est pas illusoire. Vous devez être encore plus prudent lorsque vous utilisez ce qu'on appelle la « récursivité complexe » : une fonction A()appellera une fonction B()qui appelle une fonction A(). La résolution de tels problèmes nécessite une compréhension complète du fonctionnement de la récursivité. Un exemple d'une telle tâche : calculer la valeur de x^n/(n!). La factorielle, comme nous l'avons vu ci-dessus, est définie sur l'ensemble des entiers non négatifs. Enfin, je donnerai le code de la solution. La récursivité complexe comprendra deux méthodes :

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Pour entrer en récursion, une méthode est utilisée calculate, qui appelle une méthode power, qui à son tour appelle une méthode calculate. Nous avons défini la base de récursivité dans la méthode puissance :

if (n == 1) return x;

L'étape de récursion y est également définie :

return x * calculate(x, n - 1);

Il reste à ajouter une vérification de la validité des données d'entrée :

Tout nombre autre que zéro est égal à la puissance zéro 1. Si n = 0donc n! = 1. Il faut le retourner 1.
Zéro à n’importe quelle puissance est égal à zéro.
Nous ne considérerons pas l’incertitude de type 0^0et accepterons ces données d’entrée comme invalides.

Avec toutes les vérifications, les méthodes ressembleront à ceci :

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Eh bien, lorsque vous appelez une fonction, vous devez vous rappeler de détecter l'erreur :

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}

Commentaires

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION