Réécriture récursive
La somme 1 + 2 + … + n et la pile d'appels
Réécrire sous forme récursive (et terminale quand c'est possible) des algorithmes itératifs — ici la somme des entiers de 1 à n.
1Fonction somme(n) : entier2 Si n = 0 alors3 Retourner 04 Sinon5 Retourner n + somme(n-1)6FIN1Fonction sommeT(n, acc) : entier2 Si n = 0 alors Retourner acc3 Retourner sommeT(n-1, acc+n)En transportant le résultat dans acc, l'appel récursif est la dernière opération : plus rien à faire en remontant.
La descente empile les appels jusqu'au cas de base ; la remontée combine les résultats. La forme terminale (avec accumulateur) évite ce travail au retour.
Fibonacci & les lapins
L'arbre d'appels exponentiel
Un couple de lapins engendre un nouveau couple chaque mois dès son deuxième mois. Exprimer la population du mois n, la calculer (itératif & récursif), et trouver quand elle dépasse 300.
fib(5) = fib(4) + fib(3)1Fonction fib(n) : entier2 Si n ≤ 1 alors3 Retourner n4 Sinon5 Retourner fib(n-1) + fib(n-2)6FINRemarquez la redondance : fib(2) est recalculé plusieurs fois. Le nombre d'appels explose — c'est pourquoi la version itérative est préférée en pratique.
couplesn = couplesn−1 + couplesn−2 · au mois 12 → 144 couples · la population dépasse 300 au mois 14 (377).
La relation fib(n) = fib(n-1) + fib(n-2) se traduit en un arbre binaire d'appels. Sa taille croît exponentiellement, d'où l'intérêt de la version itérative pour les grandes valeurs.
PGCD & conversion binaire
Euclide et l'affichage au retour
Écrire récursivement le PGCD de deux nombres, puis la conversion d'un décimal en binaire.
1Fonction pgcd(a, b) : entier2 Si b = 0 alors3 Retourner a4 Sinon5 Retourner pgcd(b, a mod b)6FINEuclide repose sur pgcd(a, b) = pgcd(b, a mod b) avec le cas de base b = 0. Pour le binaire, écrire après l'appel récursif produit les bits dans le bon ordre.