Scribd
Importer
58 vues3 pages

Comprendre la récursivité en algorithmique

Le document décrit la récursivité à travers des exemples comme le calcul de factorielle et du PGCD de manière itérative et récursive. Il présente également les avantages et inconvénients de la récursivité comme le chevauchement des appels et la taille limitée de la pile d'exécution.

Transféré par

Arthur BRS
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
58 vues3 pages

Comprendre la récursivité en algorithmique

Le document décrit la récursivité à travers des exemples comme le calcul de factorielle et du PGCD de manière itérative et récursive. Il présente également les avantages et inconvénients de la récursivité comme le chevauchement des appels et la taille limitée de la pile d'exécution.

Transféré par

Arthur BRS
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

Récursivité

Recursion

1. Introduction

Exemple: Soit n dans N*, factorielle n

n! = 1.2.3….n

Algorithme:

Entrée: entier n

Sortie: entier n!

Version itérative:

Def factorielle(n):

nF = 1

for i in range(2,n+1):

nF *= i

return nF

Version récursive:

Principe: Pour calculer n!, on calcule un k! Avec k < n. “Une fonction qui s’appelle elle-
même” ou plus précisément, elle résout un problème de taille n grâce à la résolution
de problèmes de k < n

Def factorielleRec(n):

if n == 1 or n == 0:

return 1

else:

return factorielleRec(n-1)*n

2. Pile d’exécution

Empile tous les appels de fonction et toutes les variables utilisées

Exemple: pile de factorielle-rec(4):

n=1, factorielle-rec(1) = 1

n=2, 2 * factorielle-rec(1)

n=3, 3 * factorielle-rec(2)

n=4, 4 * factorielle-rec(3)

3. Exemples

Algorithme d’Euclide:

PGCD(a,b) où a, b deux entiers

Version itérative:

1
def pgcd(a, b):

while b:

a, b = b, a % b

return a

Version Récursive:

print(pgcd(8,4))

def PGCDrec(a,b):

if a%b:

return b

return pgcd(b,a%b)

Exponentiation: on veut calculer xn où n >= 0

Version itérative:

Def exp(a,n):

x = a

for I in range(n):

x *= a

return x

Version récursive:

Def exp(a,n):

if n:

return 1

return a*exp(a,n-1)

Version récursive rapide:

def expo_rapide(x, n):

if n == 0:

return 1

y = expo_rapide(x, n // 2)

if n % 2 == 0:

return y * y

else:

return y * y * x

Avantage et Inconvénients

Inconvénients :

1. Chevauchement des appels récursifs

Il recalcule plusieurs fois les mêmes valeurs

2. Taille de la pile d’exécution

Si trop d’étapes, il ne peut pas tout empiler (stack over ow)

Avantage:

1. Certains problèmes sont facilement résoluble récursivement mais pas itérativement.

Tours d’Hanoï :

2
fl
3

Vous aimerez peut-être aussi