Chapitre 7 : La Récursivité
Sonia KEFI
1 ère LI
Plan
• Principe de la Récursivité
• Forme générale d’un sous_programme récursif
• Etude d’un exemple
• Mécanisme de fonctionnement de la récursivité
• Performances de la récursivité
• Récursivité indirecte ou croisée
• Choix entre itération et récursivité
• Exercice d’application
Principe de la Récursivité
• En mathématiques une fonction récursive est une
fonction qui appelle elle-même.
• Il est possible en algorithmique de définir une fonction
qui appelle elle-même, on parlera alors de fonction
récursive.
• La récursivité est une technique de programmation
alternative à l’itération qui permet de trouver,
lorsqu’elle est bien utilisée, des solutions très
élégantes à un certain nombre de problèmes.
• Une procédure ou fonction est dite récursive si son
corps contient un ou plusieurs appels à elle-même.
Forme générale d’un sous-programme
récursif
Sous-programme Nom_recursif (paramètres formels)
Variables // déclaration des variables locales
Début
Si (Condition_D'ARRET ) alors
Instructions du point d'arrêt
Sinon //----- exécution
Nom_recursif (paramètres effectifs changés) // appel récursif
Instructions
Finsi
Fin
Étude d’un exemple : La fonction
factorielle
Solution itérative Solution récursive
Fonction Factoriel ( n : Entier) : La relation de récurrence est définie par :
Entier 0!=1
Variables n ! = n * (n-1)!
i, F : Entier
Fonction Factoriel( n : Entier) : Entier
Début
Variables
F 1 F : entier
Pour i de 2 à n Faire Début
F F * i Si (n = 0) ou (n=1) Alors
FinPour F1
Sinon
Retourner (F)
F n * Factoriel(n-1)
Fin FinSi
Retourner (F)
Fin
Mécanisme de fonctionnement de la
récursivité (1)
• Il faut savoir qu’un ordinateur utilise une pile. Son rôle est de
stocker les variables locales et les paramètres d'une procédure ou
fonction.
• Une pile applique le principe LIFO (Last-In-First-Out) : le dernier
élément ajouté est le premier retiré.
• Dans une procédure ou fonction récursive, toutes les variables sont
stockées dans la pile, et empilées autant de fois qu'il y a d’appels
récursifs. Donc la pile se remplit progressivement, et si on ne fait
pas attention on arrive à un « débordement de pile » c'est-à-dire
un dépassement de sa capacité.
• Ensuite, les variables sont dépilées.
➢ Exemple de pile pour 4! : Empiler Dépiler
1
2
3
4
Mécanisme de fonctionnement de la
récursivité (2)
• Considérons le calcul de 4! par la fonction récursive
définie précédemment :
Factoriel(4) renvoie : 4 * Factoriel(3)
Factoriel(3) renvoie : 3 * Factoriel(2)
Factoriel(2) renvoie : 2 * Factoriel(1)
Factoriel(1) renvoie 1 (arrêt de la récursivité)
Dépiler
1
1*2=2
2 2*3=6
3 6*4=24
4
Performances de la récursivité (1)
• Les problèmes de mémoire et de rapidité sont les critères
qui permettent de faire le choix entre la solution itérative
et la solution récursive.
• Pour le calcul de la fonction factorielle, les différences entre
les deux solutions ne se voient pas trop. Il y a des cas ou la
différence est remarquable tels que la suite de Fibonacci.
• Le calcul de la suite de Fibonacci est le parfait contre-
exemple de la solution récursive.
• La relation de récurrence est définie par :
f0 = 1
f1 = 1
fn = fn-1 + fn-2 pour n > 1
Performances de la récursivité (2)
Solution récursive Solution itérative
Fonction Fibo( n : Entier) : Entier
Début
Fonction Fibo(n : Entier) : Entier
Si (n = 0) ou (n = 1) Alors Variables
Retourner (1) i, fn, fn_1, fn_2 : Entier
Sinon Début
Retourner(Fibo(n - 1) + Fibo(n – 2)) fn_1 1
fn_2 1
FinSi
Fin Pour i de 2 à n Faire
fn fn_1 + fn_2
fn_2 fn_1
fn_1 fn
On remarque que la fonction effectue Fin faire
deux appels, donc pour les valeurs Retourner (fn)
importantes de n on aura des temps Fin
d’exécution importants (attente du
résultat).
Schéma de calcul de Fibo (4)
Fibo(4) = Fibo(3) + Fibo(2)
= (Fibo(2) + Fibo(1)) + Fibo(2)
= ((Fibo(1) + Fibo(0)) + Fibo(1)) + Fibo(2)
= ((1 + Fibo(0)) + Fibo(1)) + Fibo(2)
= ((1 + 1) + Fibo(1)) + Fibo(2)
= (2 + Fibo(1)) + Fibo(2)
= (2 + 1) + Fibo(2)
= 3 + Fibo(2)
= 3 + (Fibo(1) + Fibo(0))
= 3 + (1 + Fibo(0))
Le nombre d'appels récursifs est donc très élevé (9 pour
= 3 + (1 + 1) Fibo(4), 15 pour Fibo(5), 25 pour Fibo(6) et 21891 pour
Fibo(20)) Cette solution n’est pas optimale.
=3+2
La méthode itérative est plus simple qui calcule
=5 simultanément Fibo(n) et Fibo(n-1).
Récursivité indirecte ou croisée (1)
• Quand un sous-programme fait appel à lui même,
comme dans le cas de la factorielle, on appelle cela
récursivité directe. Parfois, il est possible qu’un sous-
programme A fait appel à un sous programme B, qui
lui même fait appel au sous-programme A. Donc
l’appel qui part de A atteint de nouveau A après être
passé par B. On appelle cela récursivité indirecte
Exemple :
Procédure A(paramètres) Procédure B(paramètres)
Début Début
… …
B(valeurs) A(valeurs)
… …
Fin Fin
Exemple d’un algorithme récursif indirect pour vérifier la
parité d'un entier (2)
: Booléen
: Booléen
Choix entre itération et récursivité
• Le choix de la solution itérative peut être imposé par le
langage de programmation. En effet, certains langages
tels que Cobol et Basic ne sont pas récursifs.
• D’autre part, seuls les problèmes dont la solution se base
sur une relation de récurrence avec une condition de
sortie peuvent être résolus de façon récursive.
• Outre ces deux contraintes, le choix doit être fait
uniquement en fonction des critères d’efficacité
(contraintes de temps et d’espace). Si la solution
récursive satisfait ces critères, il n’y a pas lieu de
chercher systématiquement une solution itérative.
Exercice d’application
• Calculer la somme de n premiers entiers positifs.
Si n=4 alors s=4+3+2+1 s=4+s(3)
fonction som(n: entier): entier fonction som (n: entier): entier
Variables Début
i, S : entier si (n = 0) ou (n = 1) alors
Début Retourner (n)
S0 sinon
Pour i de 1 à n faire Retourner (n+som(n-1))
SS+ i Fin si
Fin Pour Fin
Retourner (S)
Fin
Exemple de fonction récursive qui ne
s’arrête pas « Fonction de Morris »
Soit la fonction récursive suivante :
Fonction g(m, n : Entier) : Entier
Variables
a: entier
Début g(1,0) = g(0,g(1,0))
= g(0,g(0,g(1,0)))
Si (m = 0) Alors
a 1 = g(0,g(0,g(0,g(1,0))))
Sinon =…
a g(m – 1, g(m,n)) Impossible de calculer g(1,0) ;
FinSi la récursivité ne s’arrête plus.
retourner(a)
Fin
• Calculer g(1,0) ?
FIN