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
DUT SRC - IUT de Marne-la-Vallée
23/01/2013
INF220 - Algorithmique
Cours 1
Récursivité et tris
Philippe Gambette
• Contact - Courriel : philippe.gambette@gmail.com (INF220 doit apparaître dans le sujet du courriel). - Avant ou après le cours. - Possibilité de poser des questions, de demander des exercices supplémentaires d'entrainement. • Notes et devoirsChez soi :
- Projet Morpion : exercices à trous à remplir au plus tard la veille des cours/TP/TD pour vous inciter à travailler régulièrement et corriger vos erreurs. Annonce sur IRIS 6 jours avant. - Note de remplissage de cours à trous et/ou note globale de TP à la fin du semestre, prenant en compte votreavancée à chaque séance.Pendant les cours :+ note F. Kerdjoudj
- Devoir final fin mai ou début juin (29 mai ?). Organisation pratique • Cours de Jean-François Berdjugin à l'IUT de Grenoble • Cours de Xavier Heurtebise à l'IUT de Provence http://x.heurtebise.free.fr • Le livre de Java premier langage, d'A. Tasso • http://xkcd.com, http://xkcd.free.frSources • Récursivité • Tris • Notions de complexité • Listes • ArbresPlan des cours du semestre • Récursivité • Tris • Notions de complexité • Listes • ArbresPlan des cours du semestre cours 1 cours 2 • Introduction à la récursivité • Traces d'exécution de fonctions récursives • Les tris • Le tri par sélection • Le tri à bulles • Complexité des trisPlan du cours 1 - Récursivité et tris • Introduction à la récursivité • Traces d'exécution de fonctions récursives • Les tris • Le tri par sélection • Le tri à bulles • Complexité des trisPlan du cours 1 - Récursivité et trisRécursivité
2 façons de le voir :
• Une mise en abyme • Une baguette magique algorithmiqueRécursivité
• Une mise en abymeLa "minute xkcd" - Jeu de rôle sur table
http://xkcd.com/244 http://xkcd.free.fr?id=244Récursivité
• Une mise en abymePhoto Ethan Clements
Récursivité
• Une mise en abymePhoto Ethan Clements
Comment dessiner ces images ?
Récursivité
• Une mise en abymePhoto Ethan Clements
Comment dessiner ces images ?
L'image contient une plus petite version
d'elle-même.Récursivité
• Une mise en abymePhoto Ethan Clements
Comment dessiner ces images ?
Pour dessiner la grande image, j'utilise le
dessin de l'image en plus petit.Récursivité
• Une mise en abymeQu'est-ce qu'une poupée russe ?
Photo Malix L.
Récursivité
• Une mise en abymeQu'est-ce qu'une poupée russe ?
Une poupée
russe est une poupée qui contient : - soit rien - soit une autre poupée russe plus petitePhoto Malix L.
Récursivité
• Une baguette magique algorithmique Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Récursivité
• Une baguette magique algorithmique Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Exemple des factorielles :
factorielle(1) = 1 factorielle(2) = 1x2 = 2 factorielle(3) = 1x2x3 = 6 factorielle(4) = 1x2x3x4 = 24Récursivité
• Une baguette magique algorithmique Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Exemple des factorielles :
Initialisation :
factorielle(1) = 1 factorielle(2) = 1x2 = 2Formule d'hérédité : factorielle(3) = 1x2x3 = 6 factorielle(4) = 1x2x3x4 = 24Récursivité
• Une baguette magique algorithmique Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Exemple des factorielles :
Initialisation :
factorielle(1) = 1factorielle(1) = 1 factorielle(2) = 1x2 = 2Formule d'hérédité : factorielle(n) = ... factorielle(n-1) ... factorielle(3) = 1x2x3 = 6 factorielle(4) = 1x2x3x4 = 24Récursivité
• Une baguette magique algorithmique Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Exemple des factorielles :
Initialisation :
factorielle(1) = 1factorielle(1) = 1 factorielle(2) = 1x2 = 2Formule d'hérédité : factorielle(n) = factorielle(n-1) x n factorielle(3) = 1x2x3 = 6 factorielle(4) = 1x2x3x4 = 24Récursivité
• Une baguette magique algorithmique Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Exemple des factorielles :
Initialisation :
factorielle(1) = 1factorielle(1) = 1 factorielle(2) = 1x2 = 2Formule d'hérédité : factorielle(n) = factorielle(n-1) x n factorielle(3) = 1x2x3 = 6 factorielle(4) = 1x2x3x4 = 24 ...x2Récursivité
• Une baguette magique algorithmique Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Exemple des factorielles :
Initialisation :
factorielle(1) = 1factorielle(1) = 1 factorielle(2) = 1x2 = 2Formule d'hérédité : factorielle(n) = factorielle(n-1) x n factorielle(3) = 1x2x3 = 6 factorielle(4) = 1x2x3x4 = 24 ...x2 x3 x4Récursivité
• Une baguette magique algorithmiqueExemple des factorielles :
- la première factorielle est 1 - pour passer de factorielle(n-1) à factorielle(n), je multiplie par nAlgorithme factorielle
Entrées :
Type de sortie :
Variable :
Début
FinRécursivité
• Une baguette magique algorithmiqueExemple des factorielles :
- la première factorielle est 1 - pour passer de factorielle(n-1) à factorielle(n), je multiplie par nAlgorithme factorielle
Entrées : entier n
Type de sortie : entier
Variable : entier resultat
Début
Si n=1 alors :
resultat ← 1 sinon : resultat ← n x factorielle(n-1)Fin si
renvoyer resultat FinRécursivité
• Une baguette magique algorithmiqueExemple des factorielles :
- la première factorielle est 1 - pour passer de factorielle(n-1) à factorielle(n), je multiplie par nAlgorithme factorielle
Entrées : entier n
Type de sortie : entier
Variable : entier resultat
Début
Si n=1 alors :
resultat ← 1 sinon : resultat ← n x factorielle(n-1)Fin si
renvoyer resultatFinentierentier
Récursivité
• Une baguette magique algorithmiqueExemple des factorielles :
- la première factorielle est 1 - pour passer de factorielle(n-1) à factorielle(n), je multiplie par nAlgorithme factorielle
Entrées : entier n
Type de sortie : entier
Variable : entier resultat
Début
Si n=1 alors :
resultat ← 1 sinon : resultat ← n x factorielle(n-1)Fin si
renvoyer resultatFinAlgorithme factorielle
Entrées : entier n
Type de sortie : entier
Variable : entier resultat
Début
resultat ← 1Pour i de 2 à n faire :
resultat ← i x resultatFinPour
renvoyer resultatFinversion non récursive :
• Introduction à la récursivité • Traces d'exécution de fonctions récursives • Les tris • Le tri par sélection • Le tri à bulles • Complexité des trisPlan du cours 1 - Récursivité et trisRécursivité
• Une baguette magique algorithmiqueExemple des factorielles :
- la première factorielle est 1 - pour passer de factorielle(n-1) à factorielle(n), je multiplie par nTrace de factorielle(4) :Algorithme factorielle
Entrées : entier n
Type de sortie : entier
Variable : entier resultat
Début
Si n=1 alors :
resultat ← 1 sinon : resultat ← n x factorielle(n-1)Fin si
renvoyer resultatFinfactorielle(4)?
Récursivité
• Une baguette magique algorithmiqueExemple des factorielles :
- la première factorielle est 1 - pour passer de factorielle(n-1) à factorielle(n), je multiplie par nTrace de factorielle(4) :
factorielle(4) factorielle(3)Algorithme factorielleEntrées : entier n
Type de sortie : entier
Variable : entier resultat
Début
Si n=1 alors :
resultat ← 1 sinon : resultat ← n x factorielle(n-1)Fin si
renvoyer resultat Fin??Récursivité
• Une baguette magique algorithmiqueExemple des factorielles :
- la première factorielle est 1 - pour passer de factorielle(n-1) à factorielle(n), je multiplie par nTrace de factorielle(4) :
factorielle(4) factorielle(3) factorielle(2) factorielle(1)???Algorithme factorielleEntrées : entier n
Type de sortie : entier
Variable : entier resultat
Début
Si n=1 alors :
resultat ← 1 sinon : resultat ← n x factorielle(n-1)Fin si
renvoyer resultat Fin?Récursivité
• Une baguette magique algorithmiqueExemple des factorielles :
- la première factorielle est 1 - pour passer de factorielle(n-1) à factorielle(n), je multiplie par nTrace de factorielle(4) :
factorielle(4) factorielle(3) factorielle(2) factorielle(1)12624Algorithme factorielleEntrées : entier n
Type de sortie : entier
Variable : entier resultat
Début
Si n=1 alors :
resultat ← 1 sinon : resultat ← n x factorielle(n-1)Fin si
renvoyer resultat FinRécursivité
Même concept que la preuve par récurrence
La "minute mathématique"
Théorème : Je sais monter une échelle
Récursivité
Même concept que la preuve par récurrence
La "minute mathématique"
Théorème : Je sais monter une échelle
Démonstration :
Initialisation : je sais monter depuis le sol jusqu'au premier barreau. Hérédité : si je sais monter jusqu'au (n-1)-ième barreau, je saurai monter jusqu'au n-ième barreau.Un autre algorithme récursif
La multiplication
Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Pour calculer a x n :
Initialisation :
Formule d'hérédité :Exemple :
a x 0 = 0 a x 1 = a a x 2 = 2a a x 3 = 3a?Un autre algorithme récursif
La multiplication
Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Pour calculer a x n :
Initialisation :
a x 0 =Formule d'hérédité :
a x n = ... a x (n-1) ...Exemple : a x 0 = 0 a x 1 = a a x 2 = 2a a x 3 = 3a?Un autre algorithme récursif
La multiplication
Si je sais construire le n-ième objet à partir du (n-1)-ième objet, et que je sais construire le premier objet, alors je sais construire tous les objets.Pour calculer a x n :
Initialisation :
a x 0 =Formule d'hérédité :
a x n = ... a x (n-1) ...Exemple :3 x 0 = 0
quotesdbs_dbs22.pdfusesText_28[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