Découvrez le fonctionnement des algorithmes

En programmation, nous avons vu que nous pouvions utiliser des boucles pour répéter une opération. Nous les appelons des boucles itératives. Laissez-moi vous présenter un nouveau concept : la récursivité.

Il s’agit d’un concept un peu spécial. Avez-vous déjà rêvé que vous rêviez ? Vous y êtes ! Nous allons parler de concepts qui s’appellent eux-mêmes. C’est parti !

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

La récursivité est un concept qui fait référence à lui-même dans son fonctionnement.

Les poupées russes sont une excellente métaphore de la récursivité. Si vous n'avez jamais joué avec des poupées russes, elles sont exactement ce à quoi elles ressemblent. Chaque poupée est la même sauf pour sa taille ; elles s'ouvrent chacune, et la poupée à l'intérieur est de plus en plus petite jusqu'à ce que vous arriviez au plus petit enfant, qui ne s'ouvre pas. Lorsque vous atteignez le plus petit enfant, vous inversez le processus en fermant chaque poupée une par une dans l'ordre inverse.

Par ailleurs, nous utilisons tous les jours la récursivité lorsque nous définissons des mots ! En effet, nous utilisons des mots pour en définir d’autres, eux-mêmes étant définis par d’autres mots !

La récursivité en programmation

En programmation, il s’agit d’une fonction qui fait référence à elle-même. Deux fonctions peuvent s’appeler l’une l’autre, on parle alors de récursivité croisée.

Essayons de retranscrire l’exemple des poupées russes à l’aide d’une fonction récursive. Nous allons alors compter le nombre de poupées à l’aide d’une fonction récursive.

Nous devons tout d’abord créer la fonction qui prend en paramètre une poupée, qu’elle contienne ou non une autre poupée :

Algorithme nombre_de_poupées(poupée)
Début

Fin

Nous pouvons maintenant construire le corps de la fonction. Si la poupée en paramètre contient une autre poupée, nous retournons 1 pour compter cette poupée, et nous appelons de manière récursive la même fonction pour vérifier si l’autre poupée contient aussi une autre poupée.

Algorithme nombre_de_poupées(poupée)
Début
    Si poupée contient une autre poupée :
        Retourner 1 + nombre_de_poupées(poupée à l’intérieur)
    Fin Si
Fin

Pour terminer, nous devons trouver un moyen d’arrêter cette fonction récursive, sinon nous aurons une boucle infinie. Ainsi, si la poupée ne contient pas de poupée, nous allons retourner 1, simplement pour comptabiliser cette poupée.

Nous avons donc cette fonction finale :

Algorithme nombre_de_poupées(poupée)
Début
    Si poupée contient une autre poupée :
        Retourner 1 + nombre_de_poupées(poupée à l’intérieur)
    Sinon
        Retourner 1
    Fin Si
Fin

Comme pour les boucles, il faut toujours penser à une condition qui permette d’arrêter les appels récursifs.

La suite de Fibonacci

Avez-vous déjà passé un entretien d’embauche technique pour travailler en tant que développeur·se, par exemple ? Si oui, la suite de Fibonacci vous parlera certainement ! Il s’agit d’un des problèmes les plus couramment posés en entretien.

La suite de Fibonacci est une liste de nombres entiers. Elle commence généralement par les nombres 0 et 1 (parfois 1 et 1). On appelle un nombre de cette liste un terme. Chaque terme est la somme des deux termes qui le précèdent.

Par exemple, si la suite de Fibonacci débute ainsi : 0, 1, 1, 2, 3, 5, 8, 13, 21, etc., vous voyez que 0 + 1 donne 1, que 1 + 2 donne 3, que 3 + 5 donne 8, et ainsi de suite.

Il existe plusieurs manières de résoudre le problème lié à la suite de Fibonacci. Prenez quelques minutes pour réfléchir aux différents algorithmes que vous pourriez inventer.

Pour résoudre ce problème, nous allons utiliser une méthode récursive et une méthode itérative, afin que vous puissiez comparer les deux possibilités !

La méthode par algorithme récursif naïf

Un algorithme naïf désigne un algorithme "simple", très proche de notre pensée quotidienne. Concrètement, il s’agit de la première manière qui vous vient à l’esprit pour résoudre un problème.

Dans notre cas, nous pouvons dire :

Algorithme fibonacci(n)
Début
    Si n <= 1:
        Retourner 1
    Sinon
        Retourner fibonacci(n - 1) + fibonacci(n - 2)
    Fin Si
Fin

Si on appelle la fonction  fibonacci  avec le paramètre 3 fibonacci(3)  ,  la fonction renverra 3. Mais pourquoi ?

• fibonacci(3)  :  appelle les fonctions fibonacci(2)  et fibonacci(1)  :

  • fibonacci(1)  :  cette fonction s’arrête et renvoie 1.

  • fibonacci(0)  : cette fonction s’arrête et renvoie 1.

  • Donc  fibonacci(2)  renvoie 1 + 1.

  • fibonacci(2)  : appelle les fonctions fibonacci(1)  et fibonacci(0)  .

  • fibonacci(1)  : cette fonction s’arrête et renvoie 1.

• Finalement on additionne ce que retournent fibonacci(2)  et fibonacci(1)  , soit 2 + 1.

Donc fibonacci(3)  = 3.

Le problème dans ce cas est que nous consommons beaucoup de mémoire. En effet, le calcul est exponentiel : il demande deux calculs différents pour se calculer lui-même.

Quand nous calculons la valeur d’un nombre, nous réalisons les trois opérations suivantes :

• calcule fibonacci(n-1) [qui lui-même va calculer fibonacci(n-1) et ainsi de suite jusqu’à arriver au chiffre 1] et garde la valeur en mémoire  ;

• calcule fibonacci(n-2) [fais-en de même à chaque fois jusqu’à arriver à 1] et garde la valeur en mémoire  ;

• enfin, ajoute les deux précédentes valeurs.

Nous voyons par conséquent que ce calcul est exponentiel : chaque nouveau nombre demande deux fois plus de mémoire que son précédent. Sa complexité est de O(2^n).

Nous avons sans doute une solution toute trouvée avec un algorithme linéaire !

La méthode par algorithme linéaire

Et si vous calculiez deux valeurs consécutives à la suite ? Cela serait mieux, non ?

Nous pouvons ainsi écrire la fonction suivante :

Algorithme fibonacci(n)
Variable
    a ← 0 : ENTIER
    b ← 1 : ENTIER
    c ← 0 : ENTIER
Début
    Pour i allant de 1 jusqu’à n:
        c ← a + b
        a ← b
        b ← c
    Retourner b
Fin

À présent, chaque nouveau nombre n’a plus besoin de deux niveaux d’opération pour le générer, mais d’un seul. Il est donc linéaire et sa complexité est de O(n).

Nous voyons ici que, dans bien des cas, nous préférerons la version itérative, car elle est moins consommatrice en mémoire. La récursivité n’est pas la solution à tous les problèmes.

Voici les étapes importantes pour programmer une fonction récursive :

1. Décomposer le problème en un ou plusieurs sous-problèmes du même type. On résout les sous-problèmes par des appels récursifs.

2. Les sous-problèmes doivent être de taille plus petite que le problème initial.

3. Enfin, la décomposition doit en fin de compte conduire à un élémentaire qui, lui, n’est pas décomposé en sous-problèmes (c’est la condition d’arrêt).

Vous vous rappelez quand nous avons décomposé l’appel de chaque fonction récursivement pour le cas de la suite de Fibonacci ? Nous avons pu identifier l'ordre d’appel de chaque fonction pour identifier le résultat final de ces appels récursifs. En fait, l’ordinateur va automatiquement empiler chaque appel de fonctions afin de connaître l’ordre des appels, et avoir des informations au sujet des fonctions actives. C’est ce qu’on appelle la pile d’exécution.

Les piles d’exécution

L’ordinateur doit retenir le résultat de tous les calculs récursifs avant de finir sa boucle. Il utilise alors ce que nous appelons une "pile d’exécution" (en anglais, stack). Celle-ci est gérée automatiquement par le système.

Prenons par exemple le cas cette fonction  main  dans le labyrinthe :

Algorithme main()
Variable
    joueur_position_x ← 0 : ENTIER
    joueur_position_y ← 0 : ENTIER
    arrivée_position_x ← 5 : ENTIER
    arrivée_position_y ← 5 : ENTIER
    clés[3] : TABLEAU CHAÎNE DE CARACTÈRES
Début
    Tant Que joueur_position_x != arrivée_position_x ET joueur_position_y != arrivée_position_y ET clés.taille() != 3:
        déplacement(joueur_position_x, joueur_position_y)
        ramasser(clés, joueur_position_x, joueur_position_y)
    Fin Tant Que
Fin

Lorsque la fonction main est appelée, on la place dans la pile d’exécution :

et elle y est tant qu’elle est active, c’est-à-dire qu’elle n’est pas terminée. 

Ensuite dans la fonction  main  , nous appelons une première fois la fonction  déplacement  dans la boucle  Tant que  , on l’ajoute ainsi dans la pile d’exécution, au-dessus de la fonction  main  .

Tout de suite après, la fonction  déplacement  se termine, donc on la déplie :

Mais dans la ligne suivante, on appelle la fonction  ramasser  donc on l’empile. On a donc maintenant :

Et la fonction  ramasser  , de la même manière, sera dépilée lorsqu’elle sera terminée, et ainsi de suite tant que la boucle est active. Lorsqu’elle se termine, la fonction main se termine aussi. Et donc on retire aussi la fonction  main  de la pile d’exécution. Quand la pile est vide, le programme est terminé !

Dans le cas d’un appel récursif, c’est exactement ce qui se passe !

Considérons la fonction récursive suivante :

Algorithme compteur(n)
    Si n > 0 :
        compteur(n - 1)
    Fin Si
    Afficher n
Fin

empile

Lorsque nous appelons la fonction  compteur  avec n=2  , nous avons la pile d’appels suivante :

Tant qu’il y a des appels récursifs de la fonction  compteur  , on les empile dans la pile d’exécution.

dépile

Lorsque la dernière fonction récursive est appelée, l’ordinateur "dépile" l’ensemble des fonctions présentes dans la pile d’exécution. Autrement dit, il va chercher dans la pile le dernier élément enregistré, et ainsi de suite jusqu’à arriver en bas de la pile. Bien pratique !

À vous de jouer !

Contexte

Pour finaliser notre labyrinthe, nous souhaitons ajouter une dernière fonctionnalité. Nous allons créer des cases pièges, qui bloqueront le joueur pendant 10 secondes à chaque fois que le joueur passera dessus.

Consigne

Vous allez pour cela créer une fonction récursive qui bloquera le joueur pendant n secondes, et qui affichera un compte à rebours du temps restant pour être débloqué. Vous appellerez cette fonction  freeze  . 

Considérez que la fonction  attendre  permet de mettre en pause le jeu pendant un certain nombre de secondes. Le nombre de secondes est passé en paramètre de la fonction.

Votre objectif : 

• Définir une fonction  freeze  qui prend en paramètre le nombre n de secondes à bloquer.

• Afficher le nombre de secondes restantes.

• Mettre en pause le jeu 1 seconde.

• Appeler récursivement la fonction  freeze  .

• Spécifier la condition d’arrêt de la fonction récursive.

Vérifiez votre travail

Voici le résultat à obtenir à l'issue de l'exercice :

Algorithme freeze(n)
    Si n == 0 :
        arrêter l’appel recursive
    Fin Si
    
    Afficher n
    attendre(1)
    freeze(n - 1)
Fin

En résumé

• Une fonction récursive est une fonction qui s'appelle elle-même pendant son exécution.

• Les étapes pour construire une fonction récursive : 

  • Décomposer le problème en un ou plusieurs sous-problèmes du même type. On résout les sous-problèmes par des appels récursifs.

  • Les sous-problèmes doivent être de taille plus petite que le problème initial.

  • Enfin, la décomposition doit en fin de compte conduire à un élémentaire qui, lui, n’est pas décomposé en sous-problèmes (c’est la condition d’arrêt).

• La pile d'exécution sert à enregistrer des informations au sujet des fonctions actives dans un programme informatique.

C’est bon, c’est promis, cette fois c’est vraiment terminé ! Bravo pour l'ensemble de votre travail tout au long du cours. Et je vous dis à tout de suite dans le dernier dernier quiz de ce cours pour valider vos connaissances. Je sais que vous adorez les quiz !