Fonctionnement de la récursivité - expliqué avec des organigrammes et une vidéo

«Pour comprendre la récursivité, il faut d'abord comprendre la récursivité.»

La récursivité peut être difficile à comprendre, en particulier pour les nouveaux programmeurs. Dans sa forme la plus simple, une fonction récursive est une fonction qui s'appelle elle-même. Laissez-moi essayer d'expliquer avec un exemple.

Imaginez que vous alliez ouvrir la porte de votre chambre et qu'elle est verrouillée. Votre fils de trois ans arrive du coin de la rue et vous fait savoir qu'il a caché la seule clé dans une boîte. («Comme lui», pensez-vous.) Vous êtes en retard au travail et vous avez vraiment besoin d'entrer dans la pièce pour récupérer votre chemise.

Vous ouvrez la boîte uniquement pour trouver… d'autres boîtes. Boîtes à l'intérieur des boîtes. Et vous ne savez pas lequel a la clé! Vous devez bientôt vous procurer cette chemise, vous devez donc penser à un bon algorithme pour trouver cette clé.

Il existe deux approches principales pour créer un algorithme pour ce problème: itératif et récursif. Voici les deux approches sous forme d'organigrammes:

Quelle approche vous semble la plus simple?

La première approche utilise une boucle while. Pendant que la pile n'est pas vide, prenez une boîte et regardez à travers. Voici un pseudocode inspiré de JavaScript qui montre ce qui se passe. (Le pseudocode est écrit comme du code, mais censé ressembler davantage à la parole humaine.)

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}

La deuxième méthode utilise la récursivité. N'oubliez pas que la récursivité est l'endroit où une fonction s'appelle elle-même. Voici la deuxième façon de pseudo-code.

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

Les deux approches accomplissent la même chose. Le but principal de l'utilisation de l'approche récursive est qu'une fois que vous l'avez comprise, elle peut être plus claire à lire. Il n'y a en fait aucun avantage en termes de performances à utiliser la récursivité. L'approche itérative avec des boucles peut parfois être plus rapide. Mais principalement la simplicité de la récursivité est parfois préférée.

De plus, étant donné que de nombreux algorithmes utilisent la récursivité, il est important de comprendre comment cela fonctionne. Si la récursivité ne vous semble toujours pas simple, ne vous inquiétez pas: je vais passer en revue quelques exemples supplémentaires.

Cas de base et cas récursif

Une chose que vous devez rechercher lors de l'écriture d'une fonction récursive est une boucle infinie. C'est alors que la fonction ne cesse de s'appeler… et ne cesse de s'appeler!

Par exemple, vous voudrez peut-être écrire une fonction de compte à rebours. Vous pouvez l'écrire récursivement en JavaScript comme ceci:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.

Cette fonction continuera à compter à rebours pour toujours. Si vous exécutez accidentellement du code avec une boucle infinie, vous pouvez appuyer sur "Ctrl-C" pour tuer votre script. (Ou, si vous utilisez parfois CodePen comme moi, vous devez ajouter «? Turn_off_js = true» à la fin de l'URL.)

Une fonction récursive doit toujours dire quand arrêter de se répéter. Il doit toujours y avoir deux parties dans une fonction récursive: le cas récursif et le cas de base. Le cas récursif est lorsque la fonction s'appelle elle-même. Le cas de base est lorsque la fonction cesse de s'appeler. Cela évite les boucles infinies.

Voici à nouveau la fonction de compte à rebours, avec un cas de base:

function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.

Ce qui se passe dans cette fonction n'est peut-être pas évident. Je vais vous expliquer ce qui se passe lorsque vous appelez la fonction de compte à rebours en passant par «5».

Nous commençons par imprimer le numéro 5 en utilisant console.log. Puisque cinq n'est pas inférieur ou égal à zéro, nous passons à l'instruction else. Là, nous appelons à nouveau la fonction de compte à rebours avec le chiffre quatre (5–1 = 4?).

Nous enregistrons le nombre 4. Encore une fois, in'est pas inférieur ou égal à zéro, nous allons donc à l'instruction else et appelons le compte à rebours avec 3. Cela continue jusqu'à ce queiégale zéro. Lorsque cela se produit, nous enregistrons le nombre zéro, puis il iest inférieur ou égal à zéro. Nous arrivons enfin à l'instruction return et sortons de la fonction.

La pile d'appels

Les fonctions récursives utilisent quelque chose appelé «la pile d'appels». Lorsqu'un programme appelle une fonction, cette fonction va au-dessus de la pile d'appels. Cela ressemble à une pile de livres. Vous ajoutez des choses une par une. Ensuite, lorsque vous êtes prêt à enlever quelque chose, vous enlevez toujours l'élément supérieur.

Je vais vous montrer la pile d'appels en action avec la factorialfonction. factorial(5)s'écrit 5! et il est défini comme ceci: 5! = 5 * 4 * 3 * 2 * 1. Voici une fonction récursive pour calculer la factorielle d'un nombre:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

Voyons maintenant ce qui se passe si vous appelez. fact(3)L'illustration ci-dessous montre comment la pile change, ligne par ligne. La case la plus haute de la pile vous indique quel appel factvous êtes actuellement.

Remarquez comment chaque appel à facta sa propre copie de x. Ceci est très important pour faire fonctionner la récursivité. Vous ne pouvez pas accéder à la copie d'une fonction différente de x.

Avez-vous encore trouvé la clé?

Revenons brièvement à l'exemple d'origine sur la recherche d'une clé dans des cases imbriquées. Souvenez-vous que la première méthode était itérative en utilisant des boucles. Avec cette méthode, vous créez une pile de cases à parcourir, de sorte que vous savez toujours quelles cases vous devez encore rechercher.

Mais il n'y a pas de pile dans l'approche récursive. Comment votre algorithme sait-il quelles boîtes vous devez encore regarder? La «pile de boîtes» est sauvegardée sur la pile. Il s'agit d'une pile d'appels de fonction à moitié terminés, chacun avec sa propre liste à moitié complète de cases à parcourir. La pile garde une trace de la pile de boîtes pour vous!

Et grâce à la récursivité, vous pouvez enfin trouver la clé et récupérer votre chemise!

Vous pouvez également regarder cette vidéo de 5 minutes que j'ai réalisée sur la récursivité. Il devrait renforcer ces concepts de récursivité.

Conclusion

J'espère que cet article vous a apporté plus de clarté sur la récursivité en programmation. Cet article est basé sur une leçon de mon nouveau cours vidéo de Manning Publications appelé Algorithms in Motion. Le cours (et aussi cet article) est basé sur l' étonnant livre Grokking Algorithms par Adit Bhargava. C'est lui qui a dessiné toutes les illustrations amusantes de cet article.

Si vous apprenez mieux à travers les livres, procurez-vous le livre! Si vous apprenez mieux à travers des vidéos, envisagez d'acheter mon cours.

Obtenez 39% de réduction sur mon cours en utilisant le code ' 39carnes '!

Et enfin, pour vraiment comprendre la récursivité, vous devez relire cet article. ?