02/12/2024
LA RECURSIVITE
MME FEHRI MEJRI HANEN
DÉFINITION
La récursivité est une méthode algorithmique qui
consiste à appeler un sous-programme dans son
propre corps.
Un sous-programme récursif est un module qui fait
appel à lui-même (jusqu’à ce qu’une condition
d’arrêt soit vérifiée),
à chaque appel, il y aura mémorisation d’une
nouvelle valeur d’un même paramètre formel.
1
02/12/2024
DÉFINITION
Un programme récursif doit avoir :
- un (ou plusieurs) point d’arrêt (condition(s) de
sortie)
- un (ou plusieurs) appel récursif.
NB: Un programme peut avoir deux solutions:
Une solution itérative (utilisant les boucles)
Une solution récursive (Pas de boucle)
DÉFINITION
Le principal avantage d’un algorithme récursif est
qu’il est plus simple et plus lisible.
Le principe problème est la définition du cas d’arrêt.
La limite technique de la récursivité est la
mémoire stockant les données intermédiaires des
sous programmes que nous appelons la pile. Cette
dernière déborde
2
02/12/2024
CALCUL DE FACTORIEL
Version itérative Version récursive
Fonction Factoriel(n:entier):entier Fonction Factoriel(n:entier):entier
Debut Debut
F←1 Si N=0 alors
Pour i de 2 à N faire retourner 1
F←F*i Sinon
Fin pour retourner N*Factoriel(N-1)
Retourner F Fin si
FIN FIN
CALCUL DE FACTORIEL
Version récursive
Facoriel(5)
Fonction Factoriel(n:entier):entier 5*Factoriel(4) Dépilement
Debut 4*Facoriel(3)
Si N=0 alors 3*Factoriel(2)
F←1 Empilement
2*Factoriel(1)
Sinon 1*Factoriel(0)
F←N*Factoriel(N-1) 1
Fin si
FIN
3
02/12/2024
SOMME RECURSIVE
Ecrire une version recursive du programme intitule “som” qui lit en paramètre
un entier positif N pour calculer et renvoyer la somme des N premiers
entiers .
Implémenter le script python correspondant à la fonction développée.
Exemple :
Pour N=6 , la somme des 6 premiers entiers est 1+2+3+4+5+6 = 21
SOMME RECURSIVE
Version récursive
Somme(6)
Fonction somme(n:entier):entier 6+somme(5) Dépilement
Debut 5+somme(4)
Si N=0 alors 4+somme(3)
retourner 0 Empilement
3+somme(2)
Sinon 2+somme(1)
retourner N+somme(N-1) 1+somme(0)
Fin si 0
FIN
4
02/12/2024
SOMME CHIFFRE CHAINE
Ecrire une version recursive du programme qui lit en paramètre une chaine
alphanumérique puis retourner la somme des chiffres de cette chaine.
Implémenter le script python correspondant à la fonction développée.
Exemple :
Pour Ch=« Bac2024 » le programme affiche 8
SOMME RECURSIVE
Version récursive
Fonction sommechiffre(ch:chaine):entier
Debut
Si long(ch)=0 alors
retourner 0
Sinon
si "0"<=ch[0]<="9« alors
retourner valeur(ch[0])+sommechiffre(sous chaine(ch,1,long(ch))
sinon
retourner sommechiffre(sous chaine(ch,1,long(ch))
Fin si
Fin si
FIN
5
02/12/2024
PUISSANCE
Version itérative Version récursive
Fonction Puissance(x,e:entier):entier Fonction Puissance(x,e:entier):entier
Debut Debut
Si e=0 alors Si e=0 alors
P←1 retourner 1
Sinon Sinon
P←1 retourner x*Puissance(x,e-1)
Pour i de 1 à e faire Fin si
P←P*x FIN
Fin pour
Fin si
Retourner P
FIN
PUISSANCE
Version récursive
Puissance(6,4)
Fonction Puissance(x,e:entier):entier 6*Puissance(6,3) Dépilement
Debut 6*Puissance( (6,2)
Si e=0 alors 6*Puissance( (6,1)
retourner 1 Empilement
6*Puissance( 6,0)
Sinon 1
retourner x*Puissance(x,e-1)
Fin si
FIN
