Chap 3: Récursivité
Définition:
Un sous-programme A peut appeler un autre sous-programme B.
Lorsqu'un sous-programme appelle lui-même on parle d'appel récursif.
La récursivité est la capacité d'un sous-programme (fonction ou
procédure) à s'appeler lui-même. Elle permet de résoudre beaucoup de
problèmes contenant des itérations complexes.
Toute méthode récursive peut-être convertie en méthode non-récursive.
Tout algorithme récursif devra contenir une condition qui assure la fin du
nombre d'appels.
Code du cours : 3afjxem 1
Récursivité
Exemple1: Procédure qui s’invoque elle-même: Calcul de la factorielle
n!=n(n-1)(n-2)…2.1 Si n≥0
0!=!1=1
n!=n(n-1)! pour n≥1
Fonction fact(x:entier):entier Fonction fact(x:entier):entier
Variables resultat, i: entier Debut
Début si x=0 alors
resultat ← 1; retourner(1)
pour i de 1 a x faire sinon
resultat * ← i retourner x*fact(x-1)
finpour Finsi
return resultat Fin Fct récursive
Fin Fct non récursive
5! = 5.4! 4! = 4.3! 3! = 3.2! 2! = 2.1! 1! = 1.0!
= 120 = 24 =6 =2 =1
N.B: La condition d’arrêt est n=0
Code du cours : 3afjxem 2
Récursivité
Comment ça marche ?
Trace pour n =3:
Fonction fact(x:entier):entier
Appel à fact (3) : Debut
3 ne vaut pas 0, donc je continue si x=0 alors
retourner(1)
j'ai besoin de fact(n-1) : je calcule fact(2) :
sinon
2 ne vaut pas 0, donc je continue retourner x*fact(x-1)
j'ai besoin de fact(n-1) : je calcule fact(1) : Finsi
Fin
1 ne vaut pas 0, donc je continue
j'ai besoin de fact(n-1) : je calcule fact(0) :
0 vaut 0, donc fact(0) renvoie 1
fact(0) vaut 1, donc fac(1) renvoie 1*fact(0)= 1*1=1
fact(1) vaut 1, donc fact(2) renvoie 2 * fact(1) = 2 * 1 = 2
fact(2) vaut 2, donc fact(3) renvoie 3 * fact(2) = 3 * 2 = 6
Code du cours : 3afjxem 3
Récursivité
Comment ça marche? Fonction fact(x:entier):entier
Trace pour n =4: Debut
Appel à fact(4) si x=0 alors
. 4*fact(3) = ? retourner(1)
. Appel à fact(3) sinon
. . 3*fact(2) = ? retourner x*fact(x-1)
. . Appel à fact(2) Finsi
. . . 2*fact(1) = ? Fin
. . . Appel à fact(1)
. . . . 1*fact(0) = ?
. . . . Appel à fact(0)
. . . . fact(0) retourne la valeur 1
. . . . 1*1
. . . fact(1) retourne la valeur 1
. . . 2*1
. . fact(2) retourne la valeur 2
. . 3*2
. fact(3) retourne la valeur 6
. 4*6
fact(4) retourne la valeur 24
Code du cours : 3afjxem 4
Récursivité
• Tout algorithme récursif devra contenir une condition qui assure
la fin du nombre d'appels ?.
6
?
• On doit toujours tester en premier la condition d'arrêt, et ensuite, si la condition
n'est pas vérifiée, lancer un appel récursif.
5
Récursivité
Exemple 2 : suite de fibonacci
Un robot peu avancer par des pas de 1 ou 2 mètres.
Calculer le nombre de façons différentes de parcourir une distance de nmètres
Distance Suite de pas Nb de
possibilités
1 1 1
2 (1,1) ou 2 2
3 (1, 1, 1) ou (1, 2) ou (2, 1) 3
4 (1,1,1,1) ou (1,1,2) ou (1,2,1) ou (2,1,1) 5
ou (2,2)
Code du cours : 3afjxem 6
Récursivité
Exemple 2 : suite de fibonacci
• Pas(n:)(Nombre de possibilités pour parcourir nmètres.
• Pas(1)=1, Pas(2)=2
• Pour n>2:
– Si premier pas = 1 mètres, il reste n-1 mètres -> Pas(n-1)
– Si premier pas = 2 mètres, il reste n-2 mètres -> Pas(n-2)
Donc, Pas(n)=Pas(n-1)+Pas(n-2)
Fonction Pas(n:entier): entier
Séquence de Fibonacci:
Début
Si n=1ou n=2alors f1 = 1
Retourne (n) f2 = 2
sinon Retourne (Pas(n-1)+Pas(n-2)) fn = fn-1 + fn-2 pour n>2
Fin
Code du cours : 3afjxem 7
Récursivité
Exemple 2 : solution itérative
Fonction U (n:entier) : entier
Variables x,y,z,i : entiers
début
si(n=0)ou(n=1) alors
retourner 1
sinon x ← 1 {u(0)}
y←1 {u(1)}
pour i allant de 2 à n faire
z ← x+y {u(n)=u(n-1)+u(n-2)}
x←y
y←z
fin pour
retourner z
Finsi
fin
Code du cours : 3afjxem 8
Récursivité
◆ Exemple 2 (suite)
Voyons l’exécution : u(4)?
Pas(4)
Pas(3) + Pas(2)
Pas(2) + Pas(1)
◆ La condition d’arrêt:
Si n=1ou n=2 alors
Retourne (n)
Code du cours : 3afjxem 9
Récursivité
◆ Exemple 2 ++: suite de fibonacci
Équations de récurrences :
■ u(0) = 0, u(1) = 1 (Base)
■ u(n) = u(n-1)+u(n-2), n>1 (récurrence)
Fonction U(n:entier):entier Condition d’arrêt
Debut modifiée
si n=0 ou n=1 alors
retourner(1)
sinon
retourner U(n-1)+U(n-2)
Finsi
Fin
Code du cours : 3afjxem 10
Récursivité
◆ Exemple 2 (suite)
Voyons l’exécution : u(4)?
u(4)
u(3) u(2)
u(2) u(1)
…….. u(1) + u(0)
Fonction U(n:entier):entier
◆ La condition d’arrêt: Debut
Si n=0 ou n=1 alors si n=0 ou n=1 alors // si (n<=1)
retourner(1)
Retourner (n) sinon
retourner U(n-1)+U(n-2)
Finsi
Fin
Code du cours : 3afjxem 11
Récursivité
Exemple 3 : procédure récursive
◆ Une procédure récursive qui permet d'afficher la valeur binaire
d'un entier positif n
Procédure binaire (n : entier) Procédure binaire (n : entier)
Variables reste:entier
Début
Début Si (n < 2) alors
Si (n>0) alors Écrire n
Reste←(n%2) sinon
binaire (n/2) binaire(n/2)
Écrire (n%2)
écrire (reste)
Finsi
Finsi Fin
Fin
Code du cours : 3afjxem 12
Récursivité
Comment ça marche?
Trace pour n =25:
Appel de binaire(25)
n = 25 donc > 0
Appel de binaire (12) Procédure binaire (n : entier)
n = 12 donc > 0 Variables reste:entier
Appel de binaire (6)
n = 6 donc > 0 Début
Appel de binaire (3) Si (n>0) alors
n = 3 donc > 0 Reste←(n%2)
Appel de binaire (1) binaire (n/2)
n = 1 donc > 0 écrire (reste)
Appel de binaire (0) Finsi
n = 0 donc Arrêt
Fin
On affiche 1%2 donc 1
On affiche 3%2 donc 1
On affiche 6%2 donc 0
On affiche 12%2 donc 0
On affiche 25%2 donc 1
Code du cours : 3afjxem 13
