Résoudre un problème par des appels contrôlés à soi-même

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• définir la récursivité et reconnaître une fonction qui s’appelle elle-même ;
• identifier le cas de base, le cas récursif et la mesure de progression ;
• expliquer la descente des appels et la remontée des résultats ;
• représenter l’empilement et le dépilement des appels dans une pile d’exécution ;
• tracer manuellement l’exécution d’un algorithme récursif ;
• transformer, lorsque cela est pertinent, une solution récursive en solution itérative ;
• comparer les avantages, les limites et les coûts des deux approches ;
• prévenir la récursion infinie et les dépassements de pile ;
• concevoir les fonctions récursives de factorielle, somme, puissance et PGCD ;
• analyser la récursivité naïve de la suite de Fibonacci ;
• effectuer une recherche récursive dans un tableau ;
• tester un algorithme récursif avec des cas normaux, limites et incorrects.

Prérequis

• maîtriser les variables, les expressions et les structures conditionnelles ;
• savoir utiliser les boucles Pour et TantQue ;
• connaître les fonctions, les paramètres et les valeurs de retour ;
• savoir manipuler un tableau à une dimension ;
• être capable de construire une table de trace.

Plan du chapitre

12.1 Principe de la récursivité

12.2 Récursivité et itération

12.3 Exemples classiques

Applications, traçage, travaux dirigés, corrigés et synthèse

Organisation pédagogique indicative

Introduction à la récursivité

La récursivité est une technique de résolution dans laquelle un sous-programme utilise sa propre définition. Au lieu de répéter explicitement des instructions avec une boucle, la fonction délègue une partie du travail à un nouvel appel portant sur une donnée plus petite ou plus simple.

Cette technique apparaît naturellement dans les problèmes définis par récurrence, dans les structures hiérarchiques et dans les stratégies de division d’un problème. Elle est particulièrement utile lorsque la solution d’un cas dépend directement de la solution d’un cas plus petit.

Cependant, une définition récursive correcte ne consiste pas seulement à écrire un auto-appel. Elle doit préciser une situation terminale, garantir une progression vers cette situation et combiner correctement le résultat obtenu lors de la remontée des appels.

12.1 Principe de la récursivité

12.1.1 Fonction qui s’appelle elle-même

Une fonction est dite récursive lorsqu’elle s’appelle directement ou indirectement pendant son exécution. Dans la récursivité directe, la fonction contient un appel à son propre nom. Dans la récursivité indirecte, une fonction A appelle une fonction B qui finit par rappeler A.

Dans ce chapitre, les exemples utilisent principalement la récursivité directe, plus simple à observer et à tracer.

Structure générale d’une fonction récursive

12.1.2 Exemple introductif : compte à rebours

L’exemple suivant affiche les entiers de N à 1. Le cas N = 0 arrête la récursion. Pour N > 0, la fonction affiche N puis s’appelle avec N - 1.

Pseudo-code

12.1.3 Cas de base

Le cas de base est une situation assez simple pour être résolue immédiatement. Il empêche la fonction de s’appeler indéfiniment. Une fonction peut posséder un seul cas de base ou plusieurs cas de base.

• Factorielle : 0! = 1 constitue le cas de base.
• Fibonacci : F(0) = 0 et F(1) = 1 constituent deux cas de base.
• Recherche dans un tableau : atteindre la fin du tableau constitue un cas d’échec.
• Recherche dichotomique : l’intervalle vide constitue un cas d’échec.

12.1.4 Cas récursif

Le cas récursif exprime la solution du problème courant à partir d’un ou plusieurs problèmes plus petits. Il comporte généralement une transformation des paramètres, un appel récursif et une combinaison du résultat.

Pour calculer la somme des entiers de 1 à N, on peut utiliser la relation Somme(N) = N + Somme(N - 1). La valeur de N diminue à chaque appel, jusqu’à N = 0.

Exemple minimal

12.1.5 Mesure de progression et terminaison

Pour justifier qu’un algorithme récursif se termine, on choisit une mesure entière et non négative qui diminue strictement à chaque appel. Cette mesure peut être la valeur de N, la taille d’un intervalle, le nombre d’éléments restant à traiter ou la hauteur d’une structure.

Une preuve élémentaire de terminaison suit donc deux idées : la mesure ne peut pas décroître indéfiniment et le cas de base est atteint lorsque cette mesure prend sa valeur minimale.

12.1.6 Empilement des appels

Chaque appel de fonction possède son propre contexte d’exécution : paramètres, variables locales, adresse de retour et état des calculs en attente. Ces contextes sont mémorisés dans une pile d’appels. Le dernier appel créé est le premier à se terminer, selon le principe LIFO : dernier entré, premier sorti.

La phase de descente crée les appels. La phase de remontée restitue les résultats dans l’ordre inverse. Une variable locale appartenant à un appel n’est pas confondue avec la variable locale portant le même nom dans un autre appel.

12.1.7 Arbre des appels

Lorsqu’un appel récursif produit plusieurs nouveaux appels, la trace prend la forme d’un arbre. La suite de Fibonacci en fournit un exemple : Fibonacci(5) appelle Fibonacci(4) et Fibonacci(3), chacun générant à son tour d’autres appels.

Arbre partiel de Fibonacci(5)

Cet arbre met en évidence des calculs répétés. Par exemple, F(3) et F(2) sont recalculés plusieurs fois. Une formulation récursive élégante peut donc être inefficace si elle duplique beaucoup de travail.

12.1.8 Contrat d’une fonction récursive

Un contrat précise les conditions d’utilisation et le résultat garanti. Il est particulièrement important en récursivité, car un paramètre incorrect peut empêcher d’atteindre le cas de base.

12.2 Récursivité et itération

12.2.1 Solution récursive

Une solution récursive exprime le problème à l’aide d’une relation entre une instance et une instance plus petite. Elle met l’accent sur la définition du problème plutôt que sur la gestion explicite de la répétition.

Factorielle récursive

12.2.2 Solution itérative

Une solution itérative utilise une boucle et des variables d’état. Elle contrôle explicitement la progression et ne crée pas une nouvelle pile d’appels pour chaque répétition.

Factorielle itérative

12.2.3 Comparaison des deux approches

12.2.4 Avantages de la récursivité

• elle traduit directement certaines définitions mathématiques ;
• elle simplifie le traitement des problèmes divisés en sous-problèmes de même nature ;
• elle rend naturelle l’exploration d’arbres, de dossiers ou de structures imbriquées ;
• elle réduit parfois le nombre de variables de contrôle visibles ;
• elle facilite certains raisonnements par induction.

12.2.5 Limites de la récursivité

• chaque appel consomme de la mémoire dans la pile d’exécution ;
• une profondeur trop grande peut provoquer un dépassement de pile ;
• les appels répétés peuvent rendre une solution lente ;
• le traçage peut devenir difficile lorsque plusieurs branches sont créées ;
• une mauvaise progression peut produire une récursion infinie ;
• certains langages limitent explicitement la profondeur des appels.

12.2.6 Risque de récursion infinie

Une récursion infinie apparaît lorsque le cas de base n’est jamais atteint. Cela peut provenir d’un cas de base absent, d’une condition erronée ou d’un argument qui ne progresse pas.

Exemple incorrect

12.2.7 Récursivité terminale

Une récursion est dite terminale lorsque l’appel récursif constitue la dernière opération exécutée par la fonction. Aucun calcul n’attend le retour de l’appel. Certains compilateurs ou interpréteurs peuvent optimiser ce cas, mais cette optimisation ne doit pas être supposée sans connaître le langage utilisé.

Factorielle avec accumulateur

Dans un cours d’algorithmique, cette forme sert surtout à comprendre le rôle d’un accumulateur et la transformation possible vers une boucle.

12.2.8 Mémoïsation et calculs répétés

La mémoïsation consiste à mémoriser les résultats déjà calculés afin de les réutiliser. Elle est utile lorsqu’un arbre récursif contient de nombreux sous-problèmes identiques, comme dans la version naïve de Fibonacci.

Cette technique échange de la mémoire contre du temps de calcul. Elle sera étudiée plus en profondeur dans les chapitres consacrés à l’optimisation ou à la programmation dynamique.

12.2.9 Comment choisir ?

12.3 Exemples classiques

12.3.1 Factorielle

Pour un entier n supérieur ou égal à 0, la factorielle n! est le produit des entiers de 1 à n. Par convention, 0! = 1.

Algorithme

Complexité : la fonction réalise n appels récursifs, donc son temps est O(n) et la profondeur de pile est O(n). Les valeurs augmentent très rapidement ; le type entier peut déborder pour des valeurs relativement petites.

12.3.2 Somme des nombres de 1 à N

La somme S(n) = 1 + 2 + ... + n peut être définie par S(0) = 0 et S(n) = n + S(n - 1).

Algorithme récursif

Cette solution est utile pour comprendre la récursivité, mais une formule directe n(n + 1) / 2 ou une boucle utilise moins de pile.

12.3.3 Suite de Fibonacci

La suite de Fibonacci est définie par F(0) = 0, F(1) = 1 et F(n) = F(n - 1) + F(n - 2) pour n ≥ 2.

Version récursive naïve

La version naïve est simple mais recalcule les mêmes valeurs. Son nombre d’appels croît très rapidement et son temps est exponentiel. La profondeur de pile reste linéaire, mais le nombre total d’appels est beaucoup plus élevé.

Version itérative efficace

12.3.4 Calcul d’une puissance

Pour un réel x et un entier naturel n, la puissance x^n peut être définie par x^0 = 1 et x^n = x × x^(n - 1).

Version récursive simple

Cette version effectue n multiplications. Une version plus efficace utilise la parité de n : si n est pair, x^n = (x^(n/2))² ; si n est impair, x^n = x × x^(n - 1).

Exponentiation rapide

12.3.5 PGCD d’Euclide

Le plus grand commun diviseur de deux entiers peut être calculé par l’algorithme d’Euclide. La relation essentielle est PGCD(a, b) = PGCD(b, a MOD b), avec le cas de base PGCD(a, 0) = |a|.

Algorithme récursif

Le second argument diminue strictement tant qu’il est non nul. La profondeur est logarithmique dans les valeurs des entrées, ce qui rend cet algorithme très efficace.

12.3.6 Recherche récursive dans un tableau

Une recherche séquentielle récursive examine l’élément d’indice i. Si la valeur est trouvée, elle retourne i. Si i atteint la taille du tableau, elle retourne -1. Sinon, elle continue avec i + 1.

Recherche séquentielle récursive

Le temps est O(n) dans le pire cas et la profondeur de pile est également O(n). Pour un tableau trié, une recherche dichotomique récursive peut réduire le temps à O(log n).

Extension : recherche dichotomique récursive

Traçage des appels récursifs

Le traçage manuel doit distinguer les appels créés, les paramètres propres à chaque appel et les valeurs retournées. Une méthode fiable consiste à numéroter les appels et à noter les opérations en attente.

Méthode de traçage

1. Écrire l’appel initial avec les valeurs de ses paramètres.
2. Évaluer la condition du cas de base.
3. Si le cas récursif est choisi, noter l’opération en attente.
4. Écrire le nouvel appel avec ses nouveaux paramètres.
5. Répéter jusqu’au cas de base.
6. Remonter les appels dans l’ordre inverse et calculer chaque valeur retournée.
7. Vérifier que le résultat final correspond au jeu d’essai.

Erreurs fréquentes et bonnes pratiques

Checklist avant validation

• Le cas de base couvre-t-il les plus petites entrées valides ?
• L’appel récursif reçoit-il une instance strictement plus petite ?
• Tous les chemins d’exécution finissent-ils par retourner une valeur ?
• Les opérations en attente combinent-elles correctement les résultats ?
• Les entrées invalides sont-elles refusées ou traitées ?
• La profondeur maximale reste-t-elle raisonnable ?
• Les mêmes sous-problèmes sont-ils recalculés inutilement ?
• Des jeux d’essai limites ont-ils été tracés ?

Travaux dirigés

Pour chaque exercice, préciser le cas de base, le cas récursif, la mesure de progression, le pseudo-code et au moins trois jeux d’essai.

Exercice 1 — Affichage descendant et ascendant

Écrire une procédure récursive qui reçoit N et affiche d’abord les entiers de N à 1, puis les entiers de 1 à N. Expliquer la position des instructions d’affichage par rapport à l’appel récursif.

Exercice 2 — Somme des chiffres

Écrire une fonction récursive qui calcule la somme des chiffres d’un entier positif. Exemple : SommeChiffres(472) = 13.

Exercice 3 — Nombre de chiffres

Écrire une fonction récursive qui détermine le nombre de chiffres d’un entier positif. Préciser le traitement de la valeur 0.

Exercice 4 — Inversion d’une chaîne

Écrire une fonction récursive qui retourne l’inverse d’une chaîne. Exemple : Inverser("ALGO") retourne "OGLA".

Exercice 5 — Palindrome

Écrire une fonction récursive qui vérifie si une chaîne est un palindrome en comparant les caractères situés aux deux extrémités.

Exercice 6 — Minimum d’un tableau

Écrire une fonction récursive qui retourne la plus petite valeur des n premiers éléments d’un tableau non vide.

Exercice 7 — Recherche dichotomique

Écrire et tracer une recherche dichotomique récursive dans le tableau trié [2, 5, 8, 12, 16, 23, 38]. Rechercher successivement 16, 2 et 10.

Exercice 8 — Conversion décimale vers binaire

Écrire une procédure récursive qui affiche la représentation binaire d’un entier positif en utilisant la division entière par 2 et le modulo 2.

Exercice 9 — Tours de Hanoï

Trois tiges A, B et C contiennent des disques de tailles différentes. Écrire la stratégie récursive permettant de déplacer N disques de A vers C en utilisant B, sans poser un grand disque sur un plus petit.

Exercice 10 — Diagnostic d’algorithmes

Pour chacun des algorithmes suivants, indiquer s’il se termine et proposer une correction si nécessaire :

Corrigés indicatifs

Corrigé 1 — Affichage descendant et ascendant

Dans la première procédure, l’affichage précède l’appel : il se produit pendant la descente. Dans la seconde, il suit l’appel : il se produit pendant la remontée.

Corrigé 2 — Somme des chiffres

La division entière par 10 supprime le dernier chiffre. La mesure de progression est le nombre de chiffres restant.

Corrigé 3 — Nombre de chiffres

La valeur 0 contient un chiffre, donc le cas n < 10 retourne 1.

Corrigé 4 — Inversion d’une chaîne

Une autre solution place le premier caractère après l’inversion du reste. L’important est que la chaîne transmise à l’appel soit plus courte.

Corrigé 5 — Palindrome

L’appel initial utilise gauche = 0 et droite = Longueur(chaine) - 1.

Corrigé 6 — Minimum d’un tableau

Précondition : n ≥ 1. Chaque appel traite un préfixe contenant un élément de moins.

Corrigé 7 — Recherche dichotomique

Pour rechercher 16, le milieu initial contient 12, puis la recherche continue à droite et trouve 16. Pour rechercher 2, elle continue à gauche jusqu’au premier élément. Pour 10, l’intervalle finit par devenir vide et la fonction retourne -1.

Corrigé 8 — Conversion décimale vers binaire

L’appel récursif est effectué avant l’affichage afin que les bits de poids fort soient affichés en premier. Pour n = 0, on peut traiter séparément l’appel initial et afficher 0.

Corrigé 9 — Tours de Hanoï

Le nombre minimal de déplacements est 2^n - 1. L’exercice illustre une récursion à deux branches et une croissance exponentielle du nombre d’actions.

Corrigé 10 — Diagnostic d’algorithmes

Synthèse du chapitre

La récursivité permet à une fonction de résoudre un problème en appelant une version plus petite d’elle-même. Une solution récursive fiable repose sur un cas de base, un cas récursif, une progression démontrable et une combinaison correcte des résultats.

Checklist de conception d’une fonction récursive

1. Définir précisément le problème et le domaine des entrées.

2. Identifier la plus petite instance résoluble directement.

3. Écrire le ou les cas de base.

4. Choisir une mesure de progression.

5. Construire un appel avec une instance strictement plus petite.

6. Déterminer comment combiner le résultat récursif avec le cas courant.

7. Tracer plusieurs appels, y compris les cas limites.

8. Évaluer la profondeur de pile et les calculs répétés.

9. Comparer avec une solution itérative lorsque cela est pertinent.

10. Tester les entrées incorrectes et documenter les préconditions.

Glossaire

Auto-évaluation