fact(n)=n*fact(n-1)
De là il vous devient très facile d’écrire une fonction fact() récursive :
Fonction fact(n:entier) :entier
Début
n←fact(n-1)
Retourne n
Fin
Cette fonction n’est pas complète car elle va s’exécuter à l’infini. Il n’y a pas de condition d’arrêt. Or, le calcul doit
continuer tant que n est supérieur à 1. Voici les passes successives pour une factorielle de 5 :
q 1 ère étape : 5>1 ? Oui : fact(5) appelle 5*fact(4)
q 2 ème étape : 4>1 ? Oui : fact(4) appelle 4*fact(3)
q 3 ème étape : 3>1 ? Oui : fact(3) appelle 3*fact(2)
q 4 ème étape : 2>1 ? Oui : fact(2) appelle 2*fact(1)
q 5 ème étape : 1>1 ? Non : fact(1) sort en retournant la valeur 1 à fact(2).
Estce fini ? Non ! Chaque fonction appelée se terminant retourne sa valeur au programme ou sousprogramme l’ayant
appelé. Donc ça continue :
q 6 ème étape : fact(2) : 2*fact(1)=2, retourne 2 à fact(3)
q 7 ème étape : fact(3) : 3*fact(2)=6, retourne 6 à fact(4)
q 8 ème étape : fact(4) : 4*fact(3)=24, retourne 24 à fact(5)
q 9 ème étape : fact(5) : 5*fact(4)=120, retourne 120 au programme appelant.
Si vous suivez l’ordre des appels<>retours vous obtenez le schéma suivant :
Les allersretours d’un appel récursif
Un algorithme un peu plus correct de fact() est donc :
Fonction fact(n :entier) :entier
Début
Si n>1 Alors
n←n*fact(n-1)
FinSi
Retourne n
Fin
- 2 -
© ENI Editions - All rigths reserved - Jonifar lina
142
De là il vous devient très facile d’écrire une fonction fact() récursive :
Fonction fact(n:entier) :entier
Début
n←fact(n-1)
Retourne n
Fin
Cette fonction n’est pas complète car elle va s’exécuter à l’infini. Il n’y a pas de condition d’arrêt. Or, le calcul doit
continuer tant que n est supérieur à 1. Voici les passes successives pour une factorielle de 5 :
q 1 ère étape : 5>1 ? Oui : fact(5) appelle 5*fact(4)
q 2 ème étape : 4>1 ? Oui : fact(4) appelle 4*fact(3)
q 3 ème étape : 3>1 ? Oui : fact(3) appelle 3*fact(2)
q 4 ème étape : 2>1 ? Oui : fact(2) appelle 2*fact(1)
q 5 ème étape : 1>1 ? Non : fact(1) sort en retournant la valeur 1 à fact(2).
Estce fini ? Non ! Chaque fonction appelée se terminant retourne sa valeur au programme ou sousprogramme l’ayant
appelé. Donc ça continue :
q 6 ème étape : fact(2) : 2*fact(1)=2, retourne 2 à fact(3)
q 7 ème étape : fact(3) : 3*fact(2)=6, retourne 6 à fact(4)
q 8 ème étape : fact(4) : 4*fact(3)=24, retourne 24 à fact(5)
q 9 ème étape : fact(5) : 5*fact(4)=120, retourne 120 au programme appelant.
Si vous suivez l’ordre des appels<>retours vous obtenez le schéma suivant :
Les allersretours d’un appel récursif
Un algorithme un peu plus correct de fact() est donc :
Fonction fact(n :entier) :entier
Début
Si n>1 Alors
n←n*fact(n-1)
FinSi
Retourne n
Fin
- 2 -
© ENI Editions - All rigths reserved - Jonifar lina
142