Scribd
Importer
54 vues7 pages

Algorithmes Récursifs et Factorielles

Le document décrit les algorithmes récursifs, y compris des exemples d'algorithmes récursifs pour le calcul de factorielle, de puissance, de somme et de PGCD. Il explique également les avantages et inconvénients des algorithmes récursifs.

Transféré par

Broulaye Diarra
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
54 vues7 pages

Algorithmes Récursifs et Factorielles

Le document décrit les algorithmes récursifs, y compris des exemples d'algorithmes récursifs pour le calcul de factorielle, de puissance, de somme et de PGCD. Il explique également les avantages et inconvénients des algorithmes récursifs.

Transféré par

Broulaye Diarra
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithmes récursifs

eni-abt© 2020 Dr Yacouba Goïta 1


Les algorithmes récursifs
➢ Un Algorithme récursif est un algorithme qui fait appel à lui-même
dans le corps de sa propre définition.
➢ Cas de base : permet de définir la condition d’arrêt de l’algorithme
récursif, c’est un cas dans lequel l’algorithme ne s’appelle pas lui-même
➢ Exemple : la fonction factorielle

Algorithme factorielle (Entrée : un entier n) : un entier


Debut
si n==0
alors retourner 1
sinon
retourner n*factorielle(n-1)
finsi
Fin

eni-abt© 2020 Dr Yacouba Goïta 2


Les algorithmes récursifs
➢ Calcule de factorielle (4)
24

factorielle(4)
4*6

4*factorielle(3) 4*3*2
Montée
Descente
4*3*factorielle(2) 4*3*2*1

4*3*2*factorielle(1) 4*3*2*1*1

4*3*2*1*factorielle(0) 4*3*2*1*1
eni-abt© 2020 Dr Yacouba Goïta 3
Algorithme du calcul de puissance
{ calcul de x a la puissance n }
Algorithme puissance(Entrée: x et n des entiers): entier

Debut
si (n=0)
alors
retourner 1
sinon
retourner x*puissance(x, n-1)
finsi
Fin

eni-abt© 2020 Dr Yacouba Goïta 4


Algorithme du calcul de la somme
{ calcul de la somme des entiers entre 1 et n }
Algorithme somme(Entrée: n): entier

Debut
si (n=1)
alors
retourner 1
sinon
retourner somme(n-1)+n;
finsi
Fin

eni-abt© 2020 Dr Yacouba Goïta 5


Algorithme du plus grand commun diviseur

{PGCD (plus grand commun diviseur)}


Algorithme PGCD (Entrée: a et b des entiers) : un entier

Debut
si (a=b)
alors
retourner a
sinon
si (a < b)
alors retourner PGCD (a, b-a)
sinon retourner PGCD(a-b, b)
Finsi
Finsi
Fin

eni-abt© 2020 Dr Yacouba Goïta 6


Avantages et Inconvénients

➢ Avantages
➢ Simple à écrire
➢ Nombre d’appels récursifs souvent facile à calculer
➢ Temps d’exécution souvent facile à estimer
➢ Inconvénients
➢ Consomme de la mémoire
➢ Couteux en temps de calcul

eni-abt© 2020 Dr Yacouba Goïta 7

Vous aimerez peut-être aussi