La récursivité
Voici une idée surprenante : une fonction peut s'appeler elle-même. C'est la récursivité. Comme les poupées russes, chaque appel en ouvre un plus petit, jusqu'à la plus petite poupée, qui ne s'ouvre plus.
Un premier exemple
Un compte à rebours, sans aucune boucle :
procédure rebours(n)
si n = 0 alors
affiche 'Décollage !'
sinon
affiche n
appelle rebours(n - 1)
fin si
fin procédure
appelle rebours(3)
Le programme affiche 3, 2, 1, puis Décollage !. Regardons ce qui se passe :
rebours(3) affiche 3, puis appelle rebours(2) ;rebours(2) affiche 2, puis appelle rebours(1) ;rebours(1) affiche 1, puis appelle rebours(0) ;rebours(0) affiche « Décollage ! » et ne rappelle rien : tout s'arrête.
Les deux règles d'or
Toute fonction récursive a besoin de deux choses :
- Un cas d'arrêt : une situation simple où la fonction répond directement, sans se rappeler (ici,
n = 0). - Un appel récursif sur un problème plus petit, qui se rapproche du cas d'arrêt (ici,
n - 1).
Sans cas d'arrêt, la fonction se rappellerait sans fin. CoddyRun arrête alors le programme avec l'erreur « Récursion trop profonde ».
Question : Dans la procédure rebours, que se passerait-il en remplaçant rebours(n - 1) par rebours(n) ? — Elle se rappellerait sans fin avec la même valeur. Le problème ne devient jamais plus petit : n n'atteint jamais 0, et les appels s'empilent jusqu'à l'erreur.
La factorielle
La factorielle de 5, notée 5!, vaut 5 × 4 × 3 × 2 × 1 = 120. On remarque que 5! = 5 × 4!. La définition parle d'elle-même : parfait pour la récursivité.
fonction fact(n)
si n <= 1 alors
retourne 1
fin si
retourne n * fact(n - 1)
fin fonction
affiche fact(5) // 120
affiche fact(10) // 3628800
fact(5) attend le résultat de fact(4), qui attend celui de fact(3)... jusqu'à fact(1), qui répond 1. Les multiplications se font alors en remontant : 1, 2, 6, 24, 120.
Lance ce programme en pas à pas (F7) : la carte montre la pile d'appels grandir, puis se vider. C'est la meilleure façon de voir la récursivité en action.
La suite de Fibonacci
Dans cette suite célèbre, chaque nombre est la somme des deux précédents : 0, 1, 1, 2, 3, 5, 8, 13...
fonction fibo(n)
si n < 2 alors
retourne n
fin si
retourne fibo(n - 1) + fibo(n - 2)
fin fonction
pour i de 0 à 10
affiche 'fibo(' + i + ') = ' + fibo(i)
fin pour
Ici, la fonction se rappelle deux fois. C'est élégant, mais coûteux : pour fibo(25), elle est appelée plus de 200 000 fois ! Une boucle ferait le même calcul bien plus vite. La récursivité n'est pas toujours le meilleur choix.
Les tours de Hanoï
Un casse-tête célèbre : déplacer une pile de disques d'un piquet à un autre, un disque à la fois, sans jamais poser un grand disque sur un petit. L'idée récursive tient en trois phrases :
- Déplacer les
n - 1 disques du dessus vers le piquet de côté. - Déplacer le grand disque vers l'arrivée.
- Déplacer les
n - 1 disques du piquet de côté vers l'arrivée.
procédure hanoi(n, depart, arrivee, cote)
si n > 0 alors
appelle hanoi(n - 1, depart, cote, arrivee)
affiche 'Disque ' + n + ' : ' + depart + ' -> ' + arrivee
appelle hanoi(n - 1, cote, arrivee, depart)
fin si
fin procédure
appelle hanoi(3, 'A', 'C', 'B')
Le programme affiche les 7 déplacements à faire pour 3 disques. Avec une boucle, ce problème serait très difficile à écrire ; en récursif, il tient en cinq lignes.
En résumé
- Une fonction récursive s'appelle elle-même sur un problème plus petit.
- Il lui faut toujours un cas d'arrêt.
- Certains problèmes (factorielle, Hanoï) s'écrivent très naturellement en récursif.
- Une boucle est souvent plus rapide : la récursivité se choisit quand elle rend le programme plus clair.
