Récursivité
3 Récursivité et travail sur les chaînes de caractères. Exercice à rendre 1 4 Récursivité et opérations sur les entiers ... [1 3
Récursivité
Récursivité. Notions introduites Récursivité def somme(n): r = 0 for i in range(n + 1): ... somme(2) = 2 + somme(1) = 2 + 1 = 3.
Algorithmique Récursivité
Récursivité et Récurrence. Deux notions très proche : informatique : récursivité ... récursivité peut entraîner un débordement de pile (stack overflow).
05/06 - 2.2.3 Récursivité gauche
Une grammaire comportant au moins un symbole non terminal récursif gauche est dite récursive gauche. (Idem droite). La récursivité gauche pose divers probl`emes
La récursivité 1 Notions sur la récursivité
si il n'y a pas de condition d'arrêt la fonction boucle à l'infini
Programmation fonctionnelle Récursivité
03-Oct-2012 (1/3) x0 = 1 xn = x ? x(n?1). 11/29. La fonction puissance. (1/3) ... Récursivité double : plusieurs appels récursifs peuvent apparaˆ?tre.
Cours 1 Récursivité et tris
23-Jan-2013 Introduction à la récursivité ... Le tri à bulles. • Complexité des tris. Plan du cours 1 – Récursivité et tris ... 3 x 1 = 3.
Cours 1 Récursivité
15-Jan-2014 Exemple : 3 x 0 = 0. 3 x 1 = 3. 3 x 2 = 6. 3 x 3 = 9. 3 x 4 = 12. +3. +3. +3. Page 36. Un autre algorithme récursif. La multiplication. Si je ...
TD 2 - La récursivité - Master 1 Bio-informatique
Cette suite est la suite : (01
Récursivité
Une structure de données liée à la récursivité. D'autres exemples. Conclusion. Récursivité. Philippe Lac retourner : 1/3*(U(n-1)+2*V(n-1)).
Comprendre la récursivité en 7 min - Je suis un dev
somme(1)=1=1+0 somme(2)=3=2+1 somme(3)=6=3+3 somme(4)=10=4+6 Renvoie 6 Renvoie 3 Renvoie 1 Renvoie 0 Cas de base 1 3 Méthode de programmation d'une fonction récursive La programmation d'une fonction de façon récursive s'e ectue selon les étapes suivantes : 1 Déterminer les paramètres de la fonction comme on le ferait pour une fonction
Searches related to récursivité 1/3
Si n est positif : on appelle f avec la valeur n-1 • Chaine d’appels avec des valeurs entières strictement décroissantes de 1 en 1 • On arrive forcément à 0 • On affiche « Hello » • On remonte la pile des appels (sans rien faire ici la récursivité est terminale) 2013-2014 Algorithmique 16
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Récursivité
Philippe Lac
(philippe.lac@ac-clermont.fr)Malika More
(malika.more@u-clermont1.fr)IREM Clermont-Ferrand
Stage Algorithmique
Année 2010-2011
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Contenu
1Définition et illustration
Introduction
Définition
Premiers exemples
2Une structure de données liée à la récursivité
Notion de pile
Récursivité et pile de programme
3D"autres exemples
Récursivité croisée
Géométrie fractale
Back tracking
Diviser pour régner
4Conclusion
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
1Définition et illustration
Introduction
Définition
Premiers exemples
2Une structure de données liée à la récursivité
Notion de pile
Récursivité et pile de programme
3D"autres exemples
Récursivité croisée
Géométrie fractale
Back tracking
Diviser pour régner
4Conclusion
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Introduction
1Définition et illustration
Introduction
Définition
Premiers exemples
2Une structure de données liée à la récursivité
Notion de pile
Récursivité et pile de programme
3D"autres exemples
Récursivité croisée
Géométrie fractale
Back tracking
Diviser pour régner
4Conclusion
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Introduction
Commençons par un petit exercice de maths du lycée. On considère la suite(un)définie pourn2Npar : u0=1 u n+1=2un+3 Sans utiliser l"expression deunen fonction den, on se propose d"écrire un algorithme qui pour un entierndonné retourne la valeur deun.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Introduction
Ce que nous avons vu la journée précédente, nous conduit à écrire :FonctionUit(n: entier)Entrée:un entier nRésultat:La v aleurdu ter meunde la suite
définie par :u0=1 et u n+1=2un+3 débutDonner àUtmpla valeur 1; pourkde1ànfaireDonner àUtmpla valeur 2Utmp+3; finRetournerUtmp;
finDéfinition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Introduction
Remarque
On remonte les calculs des termes de la suite à partir deu0 jusqu"àun. u0=1,u1=2u0+3=21+3=5 etc ...
On fera référence à cet algorithme, sous le qualificatif de version itérativeDéfinition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Introduction
On peut aussi envisager de réaliser les calculs dans le sens contraire, ce qui donne : u n=2(2(:::(2u0+3):::) +3) +3|{z} n groupes deparenthèses On peut noter que cet ordre n"est pas le plus pratique pour mener les calculs, mais il est tout à fait concevable. Nous allons voir dans la suite que cette façon de procéder est prévue dans l"algorithmique et peut apporter un grand confort dans certains cas.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Définition
1Définition et illustration
Introduction
Définition
Premiers exemples
2Une structure de données liée à la récursivité
Notion de pile
Récursivité et pile de programme
3D"autres exemples
Récursivité croisée
Géométrie fractale
Back tracking
Diviser pour régner
4Conclusion
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Définition
Définition
On dit d"une fonction qu"elle est récursive lorsqu"elle fait appel à elle-même.Remarque Le lien avec la récurrence en mathématiques n"est pas le fruit du hasard.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
1Définition et illustration
Introduction
Définition
Premiers exemples
2Une structure de données liée à la récursivité
Notion de pile
Récursivité et pile de programme
3D"autres exemples
Récursivité croisée
Géométrie fractale
Back tracking
Diviser pour régner
4Conclusion
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Revenons, à notre exemple :
l"écriture u n=2(2(:::(2u0+3):::) +3) +3 fait apparaitre un appel récursif à la séquence 2:::+3u nest égal à 2un1+3 avecun1lui-même égal à 2un2+3 la "descente» s"arrête avec la valeur deu0(égale à 1 ici).Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
L"écriture de l"algorithme récursif donne :
FonctionUrec(n: entier)Entrée:un entier n
Résultat:La v aleurdu ter meunde la suite définie par :u0=1 et u n+1=2un+3 débutsin = 0alorson retourne la valeur 1;On traite le cas trivial correspondant au
premier terme de la suite % sinonon retourne la valeur 2Urec(n1) +3; ici, n6=0donc on retourne2la valeur du terme précédent+3% fin finDéfinition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Remarque
Le testn=0 est essentiel puisqu"il assure l"arrêt des appels récursifs.+par sécurité il peut-être remplacé par n0De plus l"appel suivant se fait avec une valeur strictement
inférieure à la valeur courante du paramètre. +assure la terminaison de l"algorithme.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Traduction de l"algorithme précédent :
SCILAB
function Urec=Urec(n) if n=0 then Urec=1 else Urec=2*Urec(n-1)+3 end endfunctionXCASUrec(n) :={
si (n==0) alors return 1 sinon return 2*Urec(n-1)+3; fsi; }Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
L"écriture de l"algorithme sous sa version itérative a nécessité un travail de réflexion plus conséquent. +Mise en place d"une boucle, gestion du compteur de boucle, gestion d"un résultat intermédiaire etc... La version récursive, elle, se trouve être la simple traduction dela définition mathématique de notre suite.Dans toutes les situations, où la récurrence entre en jeu,
les algorithmes récursifs vont procurer des avantages non négligeables dans leur écriture.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Le calcul de la factorielle sous forme itérative donne :FonctionFacto(n: entier)Entrée:un entier n
Résultat:F actoriellede n
débutDonner àUtmpla valeur 1; pourkde1ànfaireDonner àUtmpla valeurkUtmp; finRetournerUtmp;
finQuestion: Ecr ireun algor ithmerécursif du calcul de n!pourn donné, puis traduire cet algorithme sousXCASouSCILAB.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
FonctionFactoRec(n: entier)Entrée:un entier n
Résultat:La v aleurdu ter meunde la suite définie par :u0=1 et u n+1=2un+3 débutsin = 0alorson retourne la valeur 1;On traite le cas trivial correspondant à
0!% sinonon retourne la valeurnFactoRec(n1); ici, n6=0donc on retournenla valeur du terme précédent % fin fin+un grand classique!Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
A travers les exemples précédents, on a pu constater qu"il est impératif :que l"appel récursif porte sur une valeur de paramètre inférieure à la valeur du paramètre précédentqu"un test de sortie soit réalisé sur une valeur précise du paramètre.Ces points sont essentiels pour assurer la terminaison de l"algorithme récursif. La preuve de correction, elle, est une preuve par récurrence. Question : qu"en est-il de l"efficacité de ces algorithmes?Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Un autre exemple : suite de Fibonacci
Considérons la suite de Fibonacci, dont on rappelle la définition ci-dessous :F0=F1=1
F n=Fn1+Fn2pourn2Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Algorithmes itératif et récursifOn sait maintenant écrire deux algorithmes différents :FonctionFib(n) %version itérativedébut
sin<2alorsretourner:1 sinonDonner àxla valeur 1;Donner àyla valeur 1;
foride2àndoDonner àtempla valeurx+y;Donner àxla valeury;
Donner àyla valeurtemp;
end retourner:y fin finFonctionFib(n) %version récursivedébut sin<2alorsretourner:1 fin retourner:Fib( n1)+Fib(n2) finDéfinition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemplesIl est à ce stade intéressant de traduire ces algorithmes, +les fichiers sont disponibles?ici?. et de comparer les temps d"exécution des versions itératives et récursives. On pourra utiliser les instructions suivantes :SCILAB la séquence d"instructionstic();FibIter(10);toc()renvoie le temps nécessaire à l"exécution deFibIter(10);la séquenceT=zeros(10,1);for i=2:2:20 do, tic();FibIter(i);T(i/2)=toc();end;permet d"obtenir plusieurs temps d"exécutionstockés dans le tableauT;l"instructionplot2d(T)donne une représentation graphique des valeurs deT.XCAS
la séquence d"instructionstime(FibRec(10))[0]renvoie le temps nécessaire à l"exécution deFibIter(10)la séquenceT=seq(time(FibRec(k))[0],k,2,20,2)permet d"obtenir plusieurs tempsd"exécution stockés dans la listeT;l"instructionplotlist(T)donne une représentation graphique des valeurs deT.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Quelques temps de calculsItératif
nT(n)00.0e-05
22.0e-05
43.0e-05
64.2e-05
85.2e-05107.0e-05
127.8e-05
148.5e-05
161.0e-04
181.1e-04
201.2e-04
nTRécursif nT(n)00.0e-05
22.0e-05
46.0e-05
61.7e-04
84.6e-04101.2e-03
123.2e-03
149.0e-03
162.3e-02
186.0e-02
201.6e-01
nTDéfinition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Quelques temps de calculs
Le constat est sans appel : l"algorithme itératif sort gagnant du duel.Par exemple : le calcul de F
20nécessite 1.6e-01 s en version
récursive contre 1.2e-04 s en version itérative, soit 1300 fois plus!Au dela de cet aspect, les courbes de temps de ces deux
versions contrastent énormément :La version itérative révèle une courbeTpratiquement proportionnelle au temps.La version récursive révèle une courbeTprésentant une croissance pratiquement exponentielle. +Le calcul de F40, par exemple, peut même se révéler plus rapide à la main.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Premiers exemples
Dans l"exemple précédent, l"algorithme récursif s"est révéléclairement peu efficace par rapport à sa version itérative.De par sa conception, cet algorithme soulève d"importants
problèmes de complexités qui seront développés dans le prochain chapitre.Mais une programmation récursive peut générer aussi d"autres problèmes et des effets de bord dont il vaut mieux avoir conscience. Nous allons donner quelques éléments d"explication.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
1Définition et illustration
Introduction
Définition
Premiers exemples
2Une structure de données liée à la récursivité
Notion de pile
Récursivité et pile de programme
3D"autres exemples
Récursivité croisée
Géométrie fractale
Back tracking
Diviser pour régner
4Conclusion
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
1Définition et illustration
Introduction
Définition
Premiers exemples
2Une structure de données liée à la récursivité
Notion de pile
Récursivité et pile de programme
3D"autres exemples
Récursivité croisée
Géométrie fractale
Back tracking
Diviser pour régner
4Conclusion
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
La pile est une structure de donnée est dite de type LIFO1:La dernière valeur entrée dans la pile est la première
sortie, c"est-à-dire accessible.Pour se représenter cette structure, il est intéressant de faire l"analogie avec une pile d"assiettes.1. Last In First Out
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
Un exemple
On dispose d"une pile d"assiettes.
Cette pile se compose d"assiettes
bleues en dehors d"une assiette qui est rouge.Ecrire un algorithme, permettant
de récupérer cette assiette rouge, afin de n"avoir plus que des assiettes bleues.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
Pour cela, nous supposerons avoir à notre disposition, les procédures2suivantes :empile(P,a)ajoute l"élémentaau sommet de la pilePet
restitue la pilePainsi modifiée.depile(P,a)enlève l"élément supérieur de la pileP, restitue
cet élément dansaet restitue la pilePsans cet élément.2. on utilise ici le terme procédure, car les paramètres peuvent être modi-
fiés par la séquence d"instructions appeléeDéfinition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est bleue : on l"enlève et on la place sur la pile voisine.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est bleue : on l"enlève et on la place sur la pile voisine.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est bleue : on l"enlève et on la place sur la pile voisine.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est bleue : on l"enlève et on la place sur la pile voisine.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est bleue : on l"enlève et on la place sur la pile voisine.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est bleue : on l"enlève et on la place sur la pile voisine.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est bleue : on l"enlève et on la place sur la pile voisine.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est bleue : on l"enlève et on la place sur la pile voisine.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
L"assiette, du sommet de la
pile, est rouge.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
On la récupère.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
Et on reconstruit notre pile.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
Et on reconstruit notre pile.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
Et on reconstruit notre pile.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
Et on reconstruit notre pile.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
Et on reconstruit notre pile.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
Et on reconstruit notre pile.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
Et on reconstruit notre pile.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
Et on reconstruit notre pile.
Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
En pratique
C"est terminé :
on a enlevé notre assiette de la pile.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Notion de pile
Algorithme
Algorithme 1:exemple d"une
gestion de pileEntrée: débutQest une pile vide;Depile(P,a);
tant quea différent de rouge faireEmpile(Q,a);Depile(P,a)
fin tant queQ n"est pas videfaireDepile(Q,b);Empile(P,b)
fin finL"algorithme, ci-contre, reçoit une pilePet la restitue débarassée de sa valeur rouge.La pile est supposée n"être
pas vide et possèder une valeur rouge.Définition et illustrationUne structure de données liée à la récursivitéD"autres exemplesConclusion
Récursivité et pile de programme
1Définition et illustration
Introduction
Définition
Premiers exemples
2Une structure de données liée à la récursivité
Notion de pile
Récursivité et pile de programme
3D"autres exemples
Récursivité croisée
quotesdbs_dbs23.pdfusesText_29[PDF] Bases d 'algorithmique
[PDF] COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE
[PDF] FICHE n°6 : PROGRAMMER DES BOUCLES - Maths-et-tiques
[PDF] fiche maternelle algorithme imprimer- pdf documents
[PDF] Fiche enseignant ALGORITHMES NIVEAU : GRANDE SECTION
[PDF] Algorithme et numération - Académie de Nancy-Metz
[PDF] L 'atelier des petites chenilles en PS Etape 1 - académie de Caen
[PDF] reproduire une suite algorithmique - Accueil DSDEN 22
[PDF] Rappels : Tableaux et Matrices
[PDF] N°96 - spécial mouvement intra 2016pub - Snes
[PDF] Algorithmique et programmation : les bases (Algo) Corrigé
[PDF] TP7 : le théor`eme du point fixe en action sous MATLAB
[PDF] Séance de travaux pratiques n° 1
[PDF] simulations, algorithmes en probabilités et statistique(s) au - Apmep
