Récursion vs Itération : Comparaison des Solutions

Bonjour ! Bienvenue dans cette nouvelle leçon.

Introduction

Dans la leçon précédente, nous avons plongé au cœur du mécanisme de la récursivité en découvrant la pile d'appels. Vous avez appris à tracer manuellement l'exécution d'une fonction récursive, en observant comment chaque appel s'empile jusqu'au cas de base, puis se dépile pour construire le résultat final.

Aujourd'hui, nous allons mettre cette connaissance en perspective. L'objectif est de comparer les solutions récursives avec les solutions itératives (celles qui utilisent des boucles Pour ou Tant que). Pour un même problème, il existe souvent ces deux manières de le résoudre. Comprendre leurs avantages et leurs inconvénients respectifs est une compétence fondamentale pour un développeur. C'est ce qui vous permettra de choisir l'outil le plus adapté et, à terme, d'écrire le "code clean" que vous visez.

1. Itération vs. Récursion : Le face-à-face

Commençons par un problème que vous connaissez bien : le calcul de la factorielle. Nous allons observer comment il peut être résolu de deux manières très différentes.

Récursif et itératif : factorielle

Le site France-ioi propose une excellente introduction qui met en parallèle les deux approches pour calculer la factorielle. Faites bien attention à la structure de chaque solution.

Lisez le début de la page, jusqu'à la section "Avantages et inconvénients". Le texte présente la définition de la factorielle, puis deux implémentations : une version itérative avec une boucle et une version récursive. Le code est en langage C, mais la logique est parfaitement transposable à notre pseudo-code.

Pour que la comparaison soit encore plus claire, voici les deux algorithmes traduits dans notre pseudo-code :

Approche Itérative (avec une boucle)
Cette version utilise une variable total qui accumule le produit au fil des tours de boucle.

Fonction Factorielle_Iterative(n : Entier) : Entier
DEBUT
    total = 1
    POUR i ALLANT DE 1 A n FAIRE
        total = total * i
    FIN POUR
    RETOURNER total
FIN

L'exécution est linéaire et facile à suivre : total vaut 1, puis 1*1, puis 1*2, puis 2*3, etc.

Approche Récursive
Cette version se définit par elle-même : la factorielle de n dépend de la factorielle de n-1.

Fonction Factorielle_Recursive(n : Entier) : Entier
DEBUT
    SI (n = 0) ALORS
        RETOURNER 1  // Cas de base
    SINON
        RETOURNER n * Factorielle_Recursive(n - 1) // Cas récursif
    FIN SI
FIN

Comme nous l'avons vu, cette version crée une chaîne d'appels qui s'empilent jusqu'à n=0, puis les résultats sont calculés lors du dépilement.

L'image suivante illustre parfaitement la différence fondamentale dans l'utilisation de la mémoire et de la pile d'appels.

Comparison of Iterative vs. Recursive Factorial Execution (Activation Records) — Cette image compare l'exécution de `factorielle(5)`. À gauche, la version **itérative** utilise un seul "contexte d'exécution" (activation record) où les variables `result` et `i` sont mises à jour. À droite, la version **récursive** empile un nouveau contexte pour chaque appel, consommant plus de mémoire sur la pile jusqu'à ce que le cas de base soit atteint et que le dépilement commence.

2. Avantages et inconvénients : Comment choisir ?

Maintenant, la question cruciale : laquelle de ces deux approches est la "meilleure" ? La vérité est qu'il n'y a pas de réponse universelle. Le choix dépend du contexte.

Récursif et itératif : Avantages et inconvénients

L'article de France-ioi que vous venez de consulter résume très bien les critères de comparaison.

Lisez maintenant la section intitulée "Avantages et inconvénients". Elle analyse les deux approches sous l'angle de la simplicité du code, du temps d'exécution et de la consommation mémoire.

Résumons les points clés de cette comparaison.

Critère	Approche Itérative (Boucle)	Approche Récursive
Lisibilité	Très claire pour les tâches séquentielles simples. Le flux est linéaire.	Souvent plus concise et élégante, surtout si le problème est naturellement récursif (ex: définition mathématique).
Performance (Vitesse)	Généralement plus rapide. Une itération de boucle est une opération très optimisée.	Généralement plus lente. Chaque appel de fonction a un coût (création du contexte, empilement, dépilement).
Mémoire	Utilise une quantité de mémoire constante et faible (quelques variables).	Utilise la pile d'appels, dont la taille augmente avec la profondeur de la récursion.
Risque d'erreur	Risque de boucle infinie si la condition d'arrêt n'est jamais atteinte.	Risque de dépassement de pile (stack overflow) si la récursion est trop profonde (cas de base manquant ou problème trop grand).

L'image ci-dessous synthétise très bien ce tableau comparatif.

Recursion vs. Iteration Comparison — Ce tableau récapitule visuellement les différences fondamentales entre la récursion et l'itération, couvrant la manière dont la répétition est gérée, les conditions de terminaison, l'utilisation de la mémoire, la taille du code et la vitesse d'exécution.

3. Étude de cas : La suite de Fibonacci

La suite de Fibonacci est un exemple célèbre où une implémentation récursive "naïve" peut être catastrophique en termes de performance. La suite est définie comme suit :

F(1) = 1
F(2) = 1
Pour n > 2, F(n) = F(n-1) + F(n-2)

La version récursive semble évidente :

Fonction Fibonacci_Recursive(n : Entier) : Entier
DEBUT
    SI (n <= 2) ALORS
        RETOURNER 1
    SINON
        RETOURNER Fibonacci_Recursive(n-1) + Fibonacci_Recursive(n-2)
FIN

Cependant, cette élégance cache un grave problème d'efficacité.

Recursion vs. Iteration - Invent with Python

L'article "Recursion vs. Iteration" de Invent with Python (en anglais) illustre brillamment ce problème. Même si le texte est en anglais, les schémas et les exemples de code sont universels et très parlants.

Parcourez les sections "Calculating the Fibonacci Sequence" et "Why the Recursive Fibonacci Algorithm Is Terrible". Observez l'algorithme itératif (qui utilise deux variables pour suivre les deux derniers nombres) et l'algorithme récursif. Concentrez-vous surtout sur le schéma de l'arbre d'appels (Figure 2-3) qui montre les calculs redondants de la version récursive.

Comme l'illustre l'article, pour calculer Fibonacci(6), l'algorithme récursif calcule Fibonacci(4) deux fois, Fibonacci(3) trois fois, etc. Le nombre d'opérations explose de manière exponentielle !

La version itérative, en revanche, est très efficace :

Fonction Fibonacci_Iterative(n : Entier) : Entier
DEBUT
    SI (n <= 2) ALORS
        RETOURNER 1
    FIN SI

    a = 1
    b = 1
    POUR i ALLANT DE 3 A n FAIRE
        temp = a + b
        a = b
        b = temp
    FIN POUR
    RETOURNER b
FIN

Cette version ne calcule chaque nombre de la suite qu'une seule fois. Pour calculer Fibonacci(40), la version itérative est quasi instantanée, tandis que la version récursive prendrait un temps considérable.

4. À vous de jouer !

Votre préférence pour la pratique est un atout. Mettons-la à profit. Votre mission est d'écrire les deux versions d'un algorithme qui calcule la somme des entiers de 1 à n (par exemple, pour n=4, le résultat est 1+2+3+4=10).

Tâche :
Sur une feuille ou dans un éditeur de texte, écrivez le pseudo-code pour les deux fonctions suivantes :

Somme_Iterative(n) : qui utilise une boucle POUR.
Somme_Recursive(n) : qui utilise un appel récursif.

Indices pour la version récursive :

Quel est le cas le plus simple que vous pouvez résoudre sans calcul ? (C'est votre cas de base).
Comment pouvez-vous exprimer Somme(n) en utilisant Somme(n-1) ?

...

Solution :

Voici les solutions possibles. Comparez-les avec ce que vous avez écrit.

Version Itérative :

Fonction Somme_Iterative(n : Entier) : Entier
DEBUT
    somme = 0
    POUR i ALLANT DE 1 A n FAIRE
        somme = somme + i
    FIN POUR
    RETOURNER somme
FIN

Version Récursive :

Fonction Somme_Recursive(n : Entier) : Entier
DEBUT
    SI (n = 0) ALORS  // Ou n=1, retournant 1
        RETOURNER 0  // Cas de base
    SINON
        RETOURNER n + Somme_Recursive(n - 1) // Cas récursif
    FIN SI
FIN

Si vos algorithmes ressemblent à ceux-ci, félicitations ! Vous avez bien saisi la différence de logique entre les deux approches.

Conclusion

Aujourd'hui, vous avez acquis une vision équilibrée de deux piliers de l'algorithmique : l'itération et la récursivité.

Les points clés à retenir :

Itération (boucles) : Rapide, efficace en mémoire, idéale pour les tâches séquentielles. Le code est parfois plus long mais le flux d'exécution est direct.
Récursivité : Peut produire un code très élégant et concis pour les problèmes qui ont une structure auto-similaire. Cependant, elle est souvent plus lente et consomme de la mémoire sur la pile d'appels.
Le choix entre les deux est un compromis qui dépend du problème, de la lisibilité souhaitée et des contraintes de performance.
Certains problèmes (comme le parcours d'arborescences de fichiers) sont si naturellement récursifs que la solution itérative deviendrait très complexe à écrire.

Et après ?

Nous avons beaucoup parlé du principal inconvénient de la récursivité : le risque de "dépassement de pile" ou stack overflow. Dans la prochaine leçon, nous allons nous concentrer spécifiquement sur ce problème. Vous apprendrez à identifier précisément pourquoi il se produit et comment l'éviter, ce qui finalisera votre compréhension des aspects pratiques de la récursivité.

Recommended resources