Algorithmique Récursivité
On appelle récursive toute fonction ou procédure qui s'appelle elle même. Algorithme Fact. Entrée : un entier positif N. Sortie : factorielle de N.
Fonctions récursives (5.1)
IFT2810 A2009
Cours 2 : La récursivité
Comment programmer une fonction récursive ? Quels sont les pièges à éviter ? 2013-2014. Algorithmique. 9. Page
Programmation fonctionnelle Récursivité
3 oct. 2012 Fonctions récursives en Ocaml. La définition d'une fonction récursive est introduite par l'adjonction du mot clé rec au mot clé let.
Fonctions récursives - Lycée Pierre Corneille
En informatique une fonction f est récursive lorsque la définition de f utilise des valeurs de f. Lycée Pierre Corneille MP. Fonctions récursives
Programmation récursive —
21 mars 2019 Pour la structure liste les fonctions de manipulation (ou ... On peut suivre les différents appels d'une fonction récursive grâce `a la ...
La récursivité Lalgorithme dEuclide Implémentation en Python
La fonction factorielle est de complexité O(n). 14 / 29. La pile d'exécution : le cas factoriel. A chaque appel récursif de la
Récursivité
4 oct. 2017 1.1 Fonction factorielle . ... 2.2 Fonctions et procédures récursives . ... La fonction factorielle fac peut être définie ainsi :.
Récursivité
programmation avec fonctions récursives. • arbre d'appels L'intérêt de cette définition récursive de la fonction somme(n) est qu'elle.
cours 2:Complexité des algorithmes récursifs
Exemple: La fonction d'Ackermann. 10. Algorithmes récursifs. Calcul de complexité. ?. La complexité d'un algorithme récursif se fait par la résolution d'
[PDF] Algorithmique Récursivité
Moyen simple et élégant de résoudre certain problème Définition On appelle récursive toute fonction ou procédure qui s'appelle elle même Algorithme Fact
[PDF] Cours 2 : La récursivité
?Tout objet est dit récursif s'il se définit à partir de lui-même ?Ainsi une fonction est dite récursive si elle comporte dans son corps au moins un
[PDF] Fonctions récursives (51) - Université de Montréal
Pour définir une fonction récursive qui inverse les éléments d'une liste il est plus facile de définir une méthode InverseListe(Aij) qui prend en entrée
[PDF] Cours No 4 : Fonctions Récursives - LIRMM
– En informatique une fonction récursive est une fonction réalisant un calcul par récurrence Exemple : une fonction récursive écrite en Scheme calculant la
[PDF] Fonctions récursives - Lycée Pierre Corneille de Rouen
En informatique une fonction f est récursive lorsque la définition de f utilise des valeurs de f Lycée Pierre Corneille MP Fonctions récursives
[PDF] La théorie des fonctions récursives et ses applications - Numdam
Les fonctions récursives constituent une classe particulière de fonctions dont les variables (en nombre fini quelconque) et les valeurs sont des entiers
[PDF] Algorithmes et programmation II : La récursivité - LIP6
Une fonction récursive est une fonction qui s'appelle elle-même S Baarir (Paris10/LIP6) Cas général : la fonction est appelée récursivement et le
[PDF] LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE
minimum est ici une fonction le mot retourne permet de dire quel est son résultat ? minimum est l'appel récursif ? En programmation fonctionnelle
[PDF] Séance 5 : Fonctions récursives et machine de Turing
Fonctions primitives récursives - Fonctions récursives partielles et récursives - Machines de Turing - Equivalence de deux modèles de calcul
[PDF] Récursivité
Le document présente des exemples de fonctions définies de façon récursive – L'objectif est de comprendre la programmation récursive de quelques fonctions
Récursivité
Des fonctions ou procédures qui s"appellent elles-mêmes4 octobre 2017
Table des matières
1 Exemples introductifs 1
1.1 Fonction factorielle . . . . . . . . . . . . . . . . . . . . . . . . . .
11.2 Suite de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . .
22 La récursivité en général 3
2.1 Algorithmes récursifs . . . . . . . . . . . . . . . . . . . . . . . . .
32.2 Fonctions et procédures récursives . . . . . . . . . . . . . . . . .
32.3 Avantages et inconvénients . . . . . . . . . . . . . . . . . . . . . .
33 Comment fonctionne la récursivité? 4
3.1 La pile d"appel . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43.2 Exemple de la factorielle . . . . . . . . . . . . . . . . . . . . . . .
43.3 Exemple de la suite de Fibonacci . . . . . . . . . . . . . . . . . .
44 Complexité d"un algorithme récursif 5
4.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54.2 Exemple de la factorielle . . . . . . . . . . . . . . . . . . . . . . .
54.3 Exemple de la suite de Fibonacci . . . . . . . . . . . . . . . . . .
54.4 Complexité exponentielle . . . . . . . . . . . . . . . . . . . . . .
61 Exemples introductifs
1.1 Fonction factorielle
La fonction factoriellefacpeut être définie ainsi : si n1alorsfac(n) = 1; sinon fac(n) =nfac(n1). Cette définition est diterécursivecarfacfait appel à elle-même. Elle est valide car : il y a un cas de base qui ne gén èrepas d"app elrécursif ; il n"y aura qu"un nombre fini d"appels récursifsavant de tomber à coup sûr sur le cas de base; cette assurance est fournie par la v ariablen, qui est décrémentée de 1 à chaque appel, et donc finit par valoir 1. Implémentation Python de la factorielle récursive : 1 def fac(n): if n<=1: return 1 else: return n*fac(n-1) ce qui est la traduction exacte de la formule de récurrence. ImplémentationPython de la factorielle non récursive :
def fac2(n): p=1 for i in range(2,n+1): p*=i return p Cette version est diteitérativecar utilise une boucle, contrairement à la pré- cédente.1.2 Suite de Fibonacci
C"est la fonctionbdéfinie par :
-b(0) = 0; -b(1) = 1; -8n2;b(n) = b(n1) + b(n2); C"est une définition récursive : chaque calcul debgénère 2 appels deb. Ce qui assure la validité de cette définition est : la présence de 2 cas de base ne gé nérantpas d"app elrécu rsif; la certitude qu"il n"y aura qu"un nom brefini d"app elsrécursifs a vantde tomber sur un cas de base; certitude qui e stfournie par la v ariablen, qui décroît strictement à chaque appel, et donc finit par valoir 0 ou 1. Implémentation Python de la suite de Fibonacci récursive : traduction (presque) mot à mot! def fib(n): if n<=1: return n else: return fib(n-1)+fib(n-2)Exercice
Écrire une version itérative de la suite de Fibonacci. Est-ce plus difficile? Est-ce plus efficace?Solution :
def fib2(n): if n<=1: return n else: a,b = 0,1 for i in range(2,n+1): a,b = b,a+b return b c"est bien plus difficile à concev oir; en rev anchec"est plus rapide à l"exécution, p ourdes raisons qu"on v erra. 22 La récursivité en général
2.1 Algorithmes récursifs
Un algorithme est ditrécursifquand sa mise en oeuvre utilise ce même algorithme. Pour être valide, cet algorithme doit impérativement vérifier les 2 contraintes de terminaison: existence d"un ou pl usieurscas de base où l"algorithme es tdirectemen t effectif; assurance qu"il n"y aura qu"un nom brefini d"app elsrécursifs a vantde déboucher sur un cas de base. Cette assurance est fournie par unevariable de contrôle: entier naturel qui doit : décroître strictemen tà c haqueapp elrécursif ; v aloir0 (ou 1) p ourles cas de base.Exemple
Pour lister les anagrammes d"un mot, on peut :
1. exclure la dernière lettre ; 2. lister tous les anagrammes du mot restan t; 3. dans c hacunde ces mots, insérer la dernière lettre à toutes le sp ositions possibles. Ici : l"utilisation récursiv ea lieu à la deuxième étap e; les cas de base son tles mots d"u nelettre ; la v ariablede con trôleest la longueur du mot.2.2 Fonctions et procédures récursives
Ce sont les implémentations d"algorithmes récursifs. Elles se caractérisent par le fait que le nom de la fonction (ou procédure) apparait dans sa déclaration. Pour déclarer une fonction récursive, vous devrez : v ousass urerqu"il y a un ev ariablede con trôle; commencer par traiter les cas de base.2.3 Avantages et inconvénients
L"avantage principal de la récursivité est la simplicité de programmation. Pour écrire un programme récursif, il suffit de : trouv ercommen tréduire le problème de taille nà un ou plusieurs pro- blèmes de taille plus petite; traduire simplemen tla relation trouv ée; v érifierla terminaison de l"algorithme.Les inconvénients sont :
la m ultiplicationdes mémoires a llouéesau sto ckagedes résultats en at- tente, qui peut devenir rédhibitoire; le nom brede calculs effectués, souv entbien plus grand qu"en program- mation itérative. 33 Comment fonctionne la récursivité?
3.1 La pile d"appel
Le principe est d"utiliser une pile, ditepile d"appel, sur laquelle on empile les calculs en attente. T outapp elà une fonction crée d"ab ord2 m émoires:1 mémoire p oursto ckerl"argumen t,noté ici x ;
1 mémoire p oursto ckerle résul tat,noté ici y .
Si le calcul de y n"est pas encore p ossible,ce qui est le cas s"il y a un appel récursif, le couple (x,y) est empilé. La pile augmente tant qu"il y a des calculs en attente. Dès qu"un calcul de y est p ossible,(x,y) est dépilé ;on récup èreainsi y , et on utilise généralement sa valeur pour faire le calcul qui est en attente au sommet de la pile. Quand la p ileest vide, le dernier y qui a été dépilé fournit le résultat.3.2 Exemple de la factorielle
def fac(n): if n<=1: return 1 else: return n*fac(n-1)On va visualiser l"évolution de la pile d"appel pourfac(5):(5;5?) (5;120)(4;4?)(4;24)(3;3?)(3;6)(2;2?)(2;2)(1;1)3.3 Exemple de la suite de Fibonacci
def fib(n): if n<=1: return n else: return fib(n-1)+fib(n-2)On va visualiser l"évolution de la pile d"appel pourfib(4):(4;?) (4;2+?) (4;3)(3;?) (3;1+?) (3;2) (2;?) (2;1+?) (2;1)(2;?) (2;1+?) (2;1) (1;1) (1;1) (0;0)(1;1) (0;0)4
4 Complexité d"un algorithme récursif
4.1 Définitions
La complexité temporelled"un algorithme est l"ordre de grandeurdu nombre d"opérations élémentaires qu"il va nécessiter pour résoudre un problème de taillen. Ce nombre est à peu près proportionnel au temps effectif de calcul. La complexité spatialed"un algorithme est l"ordre de grandeurdu nombre de mémoires qu"il va utiliser pour résoudre un problème de taille n.Dans les deux cas on di stinguela complexité :
en mo yenne; dans le meilleur des cas ; dans le pire des cas. La plus utile est la première, la plus discriminante est la dernière.4.2 Exemple de la factorielle
def fac(n): def fac2(n): if n<=1: return 1 p=1 else: return n*fac(n-1) for i in range(2,n+1): p*=i return p P ourcalcul ern!par la méthode itérative, il faut : -n1multiplications : complexité temporelleO(n);4 mémoires : complexité spatiale O(1).
P ourcalcul ern!par la méthode récursive, il faut : -ntests,n1multiplications : complexité temporelleO(n); -2nmémoires (2 à chaque appel) : complexité spatialeO(n). Les deux méthodes s"exécutent en à peu près la même durée, mais la deuxième est plus gourmande en mémoire.4.3 Exemple de la suite de Fibonacci
def fib2(n): if n<=1: return n else: a,b = 0,1 for i in range(2,n+1): a,b = b,a+b return b Nom bred"op érations: 1(+2) + (n1)(1(+2))soit une complexité tem- porelleO(n): raisonnable. Nom brede mémoires : 5 soit une complexité spatiale O(1): excellente. def fib(n): if n<=1: return n else: return fib(n-1)+fib(n-2) 5 Je noteM(n)le nombre de mémoires utilisée parfib(n):8n2; M(n) = 2 +M(n1)
car contrairement au temps,la mémoire est recyclable: on peut réutiliser celles du calcul defib(n-1)pourfib(n-2). On a directement :M(n) =M(0) + 2n
doncM(n) =O(n): la complexité spatiale est raisonnable, mais moins bonne qu"en itératif.Je noteC(n)le nombre de calculs faits pourfib(n):
8n2; C(n) = 1 +C(n1) + 1 +C(n2)
On poseU(n) =C(n) + 2car -2 est le point fixe de la récurrence :8n2; U(n) =U(n1) +U(n2)
C"est une récurrence classique qu"on résout par la méthode de l"équation carac- téristique; on trouve :U(n) =rn+snoùr=1 +p5
2 '1:6; s=1p5 2 ' 0:6 On en déduitU(n) =O(rn)puisC(n) =O(rn). La complexité temporelle est très mauvaise car exponentielle.4.4 Complexité exponentielle
Pour calculerfib(100), la machine fera de l"ordre der100opérations. Or : log10(r100) = 100log10(r)'20
ce qui signifie qu"il y aura environ1020opérations. À raison de109opérations par seconde, le calcul prendra de l"ordre de1011secondes, soit environ 3000 ans! D"une manière générale, les algorithmes qui ont une complexité temporelle du typeO(qn)avecq >1ne peuvent pas être exécutés en temps acceptable pourn grand, contrairement à ceux enO(np)qui peuvent l"être (surtout sipn"est pas trop grand). Ces derniers sont dits detype P. 6quotesdbs_dbs44.pdfusesText_44[PDF] pélican volant de marey (1882)
[PDF] dynamisme d'un cycliste
[PDF] le futurisme mouvement artistique
[PDF] futurisme caractéristiques
[PDF] futurisme définition
[PDF] l5a les clans majeurs pdf
[PDF] l5a pdf
[PDF] l5a 4eme edition pdf
[PDF] pendule élastique vertical
[PDF] l5a 4eme edition pdf download
[PDF] pendule elastique definition
[PDF] l5a 4 edition pdf
[PDF] legende des 5 anneaux 4eme edition pdf
[PDF] pendule élastique horizontal exercice