Cours 2 TD
Uploaded by Ayoub LAHDOUD on Apr 02, 2023
0 ratings · 96 views · 48 pages
AI-enhanced title
Document Information
Date uploaded
Saved
Apr 02, 2023
Original Title
cours 2 td
Copyright
© © All Rights Reserved
Share this document
Cours :
Algorithmique
Facebook
avancée Twitter
La récursivité
Email
Did you find this document useful?
AD Download to read ad-free.
Is this content inappropriate? Report this Document
La récursivité
Une construction est récursive si elle se définit à partir
d'elle-même.
Exemple : le triangle de Sierpinski
AD Download to read ad-free.
La récursivité
En informatique, un programme est dit récursif s'il s'appelle
lui même. Il s'agit donc forcément d'une fonction.
Exemple : la factorielle, n! = 1 x 2 x ... x n donc n! = n x (n-1)!
L'appel récursif est traité comme n'importe quel appel de
fonction.
AD Download to read ad-free.
La récursivité
AD Download to read ad-free.
Condition d'arrêt
Puisqu'une fonction récursive s'appelle elle-même, il est impératif
qu'on prévoit une condition d'arrêt à la récursion, sinon le
programme ne s'arrête jamais!
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.
Exemple de la factorielle :
si n ≠ 1, n! = n x (n-1)!, sinon n! = 1.
AD Download to read ad-free.
Condition d'arrêt
Trusted by over 1 million members
Try Scribd FREE for 30 days to access over 125
million titles without ads or interruptions!
Start Free Trial
Cancel Anytime.
Pile d'exécution
La récursivité fonctionne car chaque appel de fonction est différent.
L'appel d'une fonction se fait dans un contexte d'exécution propre,
qui contient :
- l'adresse mémoire de l'instruction qui a appelé la fonction
- les valeurs des paramètres et des variables définies par la
fonction
Exemple : exécution du programme Toto
AD Download to read ad-free.
Pile d'exécution
AD Download to read ad-free.
Pile d'exécution
Prévoir à l'avance le nombre d'appels d'une fonction
récursive pouvant être en cours simultanément en mémoire
est impossible.
La récursivité suppose donc une allocation dynamique de
la mémoire (à l'exécution).
Quand il n'y a pas de récursivité, on peut réserver à la
compilation les zones mémoire nécessaires à chaque appel
de fonction.
AD Download to read ad-free.
Pile d'exécution
Attention : exécuter trop d'appels de fonction fera déborder la pile
d'exécution!
AD Download to read ad-free.
Récursif versus itératif
Rappel : Itérer : répéter n fois un processus en faisant changer la
valeur des variables jusqu’a obtention du résultat.
Un calcul itératif se programme par une boucle ( pour ou tant que)
Il est souvent possible d'écrire un même algorithme en itératif
et en récursif.
Exercice:
Donner un algorithme (itératif et récursif)
qui donne la somme 1+2+3+…..+n
AD Download to read ad-free.
AD Download to read ad-free.
AD Download to read ad-free.
AD Download to read ad-free.
La récursivité
Récursivité simple
Revenons à la fonction puissance x xn.
Cette fonction peut être définie récursivement :
AD Download to read ad-free.
La récursivité
Récursivité multiple
Une définition récursive peut contenir plus d’un appel
récursif.
Nous voulons calculer ici les combinaisons Cnp en se servant
de la relation de Pascal :
Trusted by over 1 million members
Try Scribd FREE for 30 days to access over 125
million titles without ads or interruptions!
Start Free Trial
Cancel Anytime.
La récursivité
Récursivité mutuelle
La récursivité croisée consiste à écrire des fonctions qui
s'appellent l'une l'autre.
Ça peut être le cas pour la définition de la parité :
AD Download to read ad-free.
La récursivité
Récursivité mutuelle
AD Download to read ad-free.
La récursivité
Récursivité imbriquée
La récursivité imbriquée consiste à faire un appel
récursif à l'intérieur d'un autre appel récursif.
La fonction d’Ackermann est définie comme suit :
AD Download to read ad-free.
La récursivité
Exercice:
Ecrire une fonction qui calcule les valeurs de la
série de Fibonacci, définie par :
u(0) = 0
u(1) = 1
u(n) = u(n−1) + u(n−2)
Ecrivez cette fonction sous forme itérative et sous
forme récursive. Laquelle des deux variantes est
préférable ici ?
AD Download to read ad-free.
La récursivité
La forme récursive est plus facile à écrire et plus proche de la
définition de la fonction, mais elle est moins efficace que la
version itérative
AD Download to read ad-free.
La récursivité
Principe et dangers de la récursivité
Principe et intérêt :
Les mêmes que ceux de la démonstration par récurrence en
mathématiques.
On doit avoir :
– un certain nombre de cas dont la résolution est connue, ces «
cas simples » formeront les cas d’arrêt de la récursion;
– un moyen de se ramener d’un cas « compliqué » à un cas « plus
simple ».
AD Download to read ad-free.
Récursivité terminale et non terminale
Une fonction récursive est dite terminale si aucun traitement
n'est effectué à la remontée d'un appel récursif (sauf le retour
d'une valeur).
Une fonction récursive est dite non terminale si le résultat de
l'appel récursif est utilisé pour réaliser un traitement (en plus du
retour d'une valeur).
Exemple de non terminalité : forme récursive non terminale de la
factorielle, les calculs se font à la remontée.
AD Download to read ad-free.
Récursivité terminale et non terminale
AD Download to read ad-free.
Récursivité terminale et non terminale
Exemple de terminalité :
Forme récursive terminale de la factorielle, les
calculs se font à la descente.
AD Download to read ad-free.
Intérêt de la récursivité terminale
Une fonction récursive terminale est en théorie plus
efficace (mais souvent moins facile à écrire) que son
équivalent non terminale : il n'y a qu'une phase de
descente et pas de phase de remontée.
En récursivité terminale, les appels récursifs n'ont pas
besoin d'êtres empilés dans la pile d'exécution car l'appel
suivant remplace simplement l'appel précédent dans le
contexte d'exécution.
Trusted by over 1 million members
Try Scribd FREE for 30 days to access over 125
million titles without ads or interruptions!
Start Free Trial
Cancel Anytime.
Intérêt de la récursivité terminale
Certains langages utilisent cette propriété pour exécuter
les récursions terminales aussi efficacement que les
itérations (ce n'est pas le cas de Java).
Il est possible de transformer de façon simple une fonction
récursive terminale en une fonction itérative : c'est la
dérécursivation.
AD Download to read ad-free.
Dérécursivation
Dérécursiver, c’est transformer un algorithme
récursif en un algorithme équivalent ne contenant
pas d’appels récursifs.
Récursivité terminale
Définition :
Un algorithme est dit récursif terminal s’il ne
contient aucun traitement après un appel récursif.
AD Download to read ad-free.
Dérécursivation
AD Download to read ad-free.
Dérécursivation
Exemple : dérécursivation de la factorielle terminale
AD Download to read ad-free.
Dérécursivation
Une fonction récursive non terminale a pour forme générale :
La fonction itérative correspondante doit gérer la sauvegarde des
contextes d'exécution (valeurs des paramètres de la fonction.
La fonction itérative correspondante est donc moins efficace qu'une
fonction écrite directement en itératif.
AD Download to read ad-free.
Dérécursivation
Remarques
Les programmes itératifs sont souvent plus efficaces.
mais les programmes récursifs sont plus faciles à écrire.
Les compilateurs savent, la plupart du temps, reconnaître les
appels récursifs terminaux, et ceux-ci n’engendrent pas de surcoût
par rapport à la version itérative du même programme.
Il est toujours possible de dérécursiver un algorithme récursif.
AD Download to read ad-free.
Complexité et récursivité
Exemple : calcul récursif de la factorielle
Paramètre de complexité : la valeur de n
Il n'y a qu'un seul cas d'exécution (pas de cas au pire ou au mieux)
Si n ≠ 1, le calcul de la factorielle de n coûte une comparaison
d'entiers, le calcul de la factorielle de n-1 et une multiplication
d'entiers.
Si n = 1, le calcul de la factorielle coûte une comparaison d'entiers.
AD Download to read ad-free.
Factorielle récursive
On pose une équation de récurrence :
appelons c(n) la complexité
c(n) = ce + c(n-1) + oe si n ≠ 1
c(1) = ce
On résoud cette équation de récurrence :
c(n) = n*ce + (n-1)*oe = O(n)
La complexité de la factorielle récursive est donc linéaire, comme
celle de la factorielle itérative.
A l'exécution, la fonction récursive est un peu moins rapide
(pente de la droite plus forte) du fait des appels récursifs
AD Download to read ad-free.
Complexité et récursivité
En général, dérécursiver un algorithme ne change pas la forme
de sa complexité, pas plus que passer en récursivité terminale!
Il existe diverses techniques pour la résolution des équations de
récurrence (méthode des fonctions génératrices et décomposition
des fractions rationnelles, transformée en Z, …).
Theoreme : soit T(n) une fonction définie par l'e=équation de
récurrence suivante, où b ≥ 2, k ≥ 0, a > 0, c > 0 et d >0 :
T(n) = a*T(n/b) + c*nk
si a > bk alors T(n)=Θ (nlogb(a))
si a = bk alors T(n)=Θ (nk*log(n))
si a < bk alors T(n)=Θ (nk)
AD Download to read ad-free.
En conclusion
-Les algorithmes récursifs sont simples (c’est simplement une autre
façon de penser).
-Les algorithmes récursifs permettent de résoudre des problèmes
complexes.
-Il existe deux types de récursivités :
-terminale, qui algorithmiquement peuvent être
transformée en algorithme non récursif.
-non terminale
-Les algorithmes récursifs sont le plus souvent plus gourmands en
ressource que leurs équivalents itératifs.
AD Download to read ad-free.
Exercice 1
Réécrire les algorithmes suivants sous forme
récursive sous forme terminal quand c’est possible.
AD Download to read ad-free.
AD Download to read ad-free.
Solution
AD Download to read ad-free.
Exercice 2
a – Ecrire un algorithme qui calcule le maximum de
2 nombres réels
b – Ecrire un algorithme récursif qui calcule le
maximum de 3 nombres réels en utilisant
l’algorithme du a. Montrer l’arbre d’appels.
c – Ecrire un algorithme récursif qui calcule le
maximum de 4 nombres réels en utilisant
l’algorithme du a. Montrer l’arbre d’appels.
d – L’algorithme est-il récursif ?
AD Download to read ad-free.
Solution
a b
Ici, Maximum2 fait office de condition terminal
de l’algorithme récursif. La pile d’appels est la
suivante :
Download to read ad-free.
c d
Bien qu’on ait l’impression de
faire une récursion, il s’agit plutôt
d’une surcharge de fonction ou
La pile d’appels est la suivante : d’appel de fonction pour réduire la
taille du problème. Ce n’est pas un
algorithme récursif à proprement
parler.
Download to read ad-free.
Exercice 3
a – Est-ce que les algorithmes ci-dessous sont des algorithmes
récursifs ?
b – Est-ce qu’ils sont terminaux ?
c – Est-ce qu’ils se terminent ?
Download to read ad-free.
Download to read ad-free.
Solution
a–
Les algorithmes log et somme sont récursifs : chacun contient au moins un appel à lui même, par
contre, puissance ne l’est pas : il fait appel à l’algorithme puis. Il faut remplacer puis par puissance.
b–
log est terminal, puissance et somme ne le sont pas car ils demandent un calcul lors de la
récursion.
c–
log se termine pour tout entier x. L’itération de la division entière par 2 mène à 0, et le cas de base 0
se termine par l’exécution de retourner.
Pour l’algorithme puissance (corrigé), le cas de base 0 se termine par l’excéution de retourner. Si
l’algorithme se termine pour la valeur n−1 alors il se termine aussi pour la valeur n est exécutant
retourner. N’oubliez pas qu’un utilisateur peut rentrer n’importe quoi comme puissance(2, – 5) donc
il faut bien vérifier sa terminaison.
somme ne se termine pas lorsque n est strictement positif. En effet, l’algorithme pour n se termine
seulement si l’algorithme se termine pour n+1. Or, il n’existe pas d’entier strictement positif pour
lesquels l’agorithme s’arrête.
Download to read ad-free.
Exercice 4
Écrivez un programme pour convertir un
nombre décimal en binaire en utilisant la
récursivité.
Download to read ad-free.
Solution
Download to read ad-free.
Share this document
You might also like
Document 16 pages
Séance 1
Safa Zehi
No ratings yet
Document 11 pages
Cours Algo2 Chapitre1
David Kevin Ovenga
No ratings yet
Document 14 pages
Cours 3
Amel Jouini
No ratings yet
Magazines Podcasts
Sheet music
Document 34 pages
Cours 1
med
No ratings yet
Document 37 pages
Chapitre 6 PDF
Monia Ghazouani
No ratings yet
Document 20 pages
Chapitre 1 - Algorithmes
Iteratif Et Recursif
نفيد%ام
No ratings yet
Document 42 pages
Compléxité
bassem rebai
No ratings yet
Document 8 pages
Chap - 1 - recursiviteIF410
(Mode de Compatibilité)
Mourtala Harouna Moussa
No ratings yet
Document 11 pages
Cours Complexité -
Algorithmique: Outline
joel
No ratings yet
Document 61 pages
Chapitre2 Recursivité
Complexité PDF
Feten Nabi
No ratings yet
Document 17 pages
La Recursivite PDF
Jessy Landry Inaka
No ratings yet
Document 31 pages
1 M3103 Algorithmique -
Avancee Recursivite
MANAL BENNOUF
No ratings yet
Show more
About Support
About Scribd Help / FAQ
Everand: Ebooks & Accessibility
Audiobooks
Purchase help
SlideShare
AdChoices
Press
Join our team! Social
Contact us Instagram
Invite friends Twitter
Scribd for enterprise
Facebook
Pinterest
Legal
Terms
Privacy
Copyright
Cookie Preferences
Do not sell or share my
personal information
Get our free apps
Documents
Language: English
Copyright © 2024 Scribd Inc.
Saved