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
1 de 11
Algorithmique
Récursivité
Florent Hivert
Mél :Florent.Hivert@lri.fr
Adresse universelle :http://www.lri.fr/˜hivert
2 de 11
Récursivité et Récurrence
Deux notions très proche :mathématiques : récurrence informatique : récursivité De nombreuses définitions mathématiques sont récursives :Définition (Peano)0 est un entier naturel.
Tout entierna un successeur uniqueSn(=n+1);Tout entier sauf0est le successeur d"un unique entier;Pour tout énoncéP(n)siP(0)est vrai et si pour toutn,P(n)
impliqueP(Sn)alors l"énoncé8n:P(n)est vrai.3 de 11
Définition
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 FactEntrée : un entier positif N
Sortie : factorielle de N
si N = 0 retourner 1 sinon retourner N x Fact(N-1)4 de 11
Exemple dans un vrai langage de programmation
unsigned int fact(unsigned int N) if (N == 0) return 1; else return N*fact(N-1);4 de 11
Exemple dans un vrai langage de programmation
unsigned int fact(unsigned int N) if (N == 0) return 1; else return N*fact(N-1);Ça marche!!!
5 de 11
Comment ça marche?
Appel à fact(4)
. 4*fact(3) = ? . Appel à fact(3) . . 3*fact(2) = ? . . Appel à fact(2) . . . 2*fact(1) = ? . . . Appel à fact(1) . . . . 1*fact(0) = ? . . . . Appel à fact(0) . . . . Retour de la valeur 1 . . . . 1*1 . . . Retour de la valeur 1 . . . 2*1 . . Retour de la valeur 2 . . 3*2 . Retour de la valeur 6 . 4*6Retour de la valeur 24
6 de 11
Notion de pile d"exécution
Définition (Pile d"exécution)
LaPile d"exécution(call stack) du programme en cours est un emplacement mémoire destiner à mémo riserles pa ramètres,les variables locales ainsi que l"adresse de retour de chaque fonction en cours d"exécution.Elle fonctionne selon le principe LIFO (Last-In-First-Out) : dernier entré premier sorti.Attention!
La pile à une taille fixée, une mauvaise utilisation de la récursivité peut entraîner un débordement de pile (stack overflow).6 de 11
Notion de pile d"exécution
Définition (Pile d"exécution)
LaPile d"exécution(call stack) du programme en cours est un emplacement mémoire destiner à mémo riserles pa ramètres,les variables locales ainsi que l"adresse de retour de chaque fonction en cours d"exécution.Elle fonctionne selon le principe LIFO (Last-In-First-Out) : dernier entré premier sorti.Attention!La pile à une taille fixée, une mauvaise utilisation de la récursivité peut entraîner un débordement de pile (stack overflow).6 de 11
Notion de pile d"exécution
Définition (Pile d"exécution)
LaPile d"exécution(call stack) du programme en cours est un emplacement mémoire destiner à mémo riserles pa ramètres,les variables locales ainsi que l"adresse de retour de chaque fonction en cours d"exécution.Elle fonctionne selon le principe LIFO (Last-In-First-Out) : dernier entré premier sorti.Attention!La pile à une taille fixée, une mauvaise utilisation de la récursivité peut entraîner un débordement de pile (stack overflow).7 de 11
Point terminal
Retenir
Comme dans le cas d"une boucle, il faut un cas d"arrêt où l"on ne fait pas d"appel récursif.procédure récursive(paramètres): si TEST_D"ARRET: instructions du point d"arrêt sinon instructions récursive(paramètres changés); // appel récursif instructions8 de 11
Détail d"un appel de fonction
PA =Programme App elant F=F onctionapp elée1LeP Aréserveet initialise les pa ramètressur la pile 2transfert du contrôle duP AàF avec
enregistrement de l"adresse de retoursur la pile3réservation sur la pile des variables locales deF Retenir
L"ensemble : paramètres + adresse de retour + variables localesconstitue leTableau d"activation (Stack Frame)deF 4exécution du code deF dansson T Ajusqu"à return5désallocation du TA deF dela pile 6retour auP Aàl"adresse enregistrée à l"étap e2, avec
transmission de lavaleur de retourdans le cas échéant9 de 11
La récursivité terminale
Définition
On dit qu"un fonction est récursive terminale, si tout appel récursif est de la formereturn f(...)Autrement dit, la valeur retournée est directement la valeur obtenue par un appel récursif, sans qu"il n"y ait aucune opération sur cette valeur. Il n"y a ainsi rien à retenir sur la pile.Entrée : Entiers positifs n, a
Sortie : a*n!
si n == 0 retourner a sinon retourner Algo(n-1,n*a)9 de 11
La récursivité terminale
Définition
On dit qu"un fonction est récursive terminale, si tout appel récursif est de la formereturn f(...)Autrement dit, la valeur retournée est directement la valeur obtenue par un appel récursif, sans qu"il n"y ait aucune opération sur cette valeur. Il n"y a ainsi rien à retenir sur la pile.Entrée : Entiers positifs n, aSortie : a*n!
si n == 0 retourner a sinon retourner Algo(n-1,n*a)10 de 11
La récursivité terminale (2)
Idée : Il n"y a rien à retenir sur la pile.Retenir Quand une fonction est récursive terminale, on peut transformer l"appel récursif en une boucle, sans utilisation de mémoire supplémentaire.Attention!cette optimisation n"est pas supp ortéepa rtous les compilateurs et est optionnelle (ex :-O3avecgcc). si n == 0 retourner a sinon retourner Algo(n-1,n*a)Devient :
Tant que n <> 0:
a <- n*a; n <- n-1 retourner a10 de 11
La récursivité terminale (2)
Idée : Il n"y a rien à retenir sur la pile.Retenir Quand une fonction est récursive terminale, on peut transformer l"appel récursif en une boucle, sans utilisation de mémoire supplémentaire.Attention!cette optimisation n"est pas supp ortéepa rtous les compilateurs et est optionnelle (ex :-O3avecgcc). si n == 0 retourner a sinon retourner Algo(n-1,n*a)Devient :
Tant que n <> 0:
a <- n*a; n <- n-1 retourner a11 de 11
La récursivité terminale (3)
L"optimisation peut se faire appel par appel.Retenir Quand une appel est récursive terminal, on peut le transformer en un saut, sans utilisation de mémoire supplémentaire.Exemple : le tri rapide tri_rapide(tableau T, entier premier, entier dernier) si premier < dernier alors pivot := choix_pivot(T, premier, dernier) pivot := partitionner(T, premier, dernier, pivot) tri_rapide(T, premier, pivot-1) // Non terminal tri_rapide(T, pivot+1, dernier) // terminalquotesdbs_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