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
Cours 2 : La récursivité
Principe
Utilisation
Exemples
Le principe de récursivité
Tout objet est dit récursif s"il se définit à partir de lui-mêmeAinsi, une fonction est dite récursive si elle comporte, dans son corps, au moins un appel à elle-mêmeDe même, une structure est récursive si un de ses attributs en est une autre instance2013-2014 Algorithmique2
CorrespondancemathématiquePrincipe de récurrenceExemple : définition des entiers (Peano)•0 est un entier•Si nest un entier, alors n+1 est un entier2013-2014 Algorithmique3
Exemples de fonctions
récursivesCalcul de la somme des entiers
de 1 à n•On calcule la somme jusqu"à n-1•Puis on ajoute nIdem avec le produit (fonction
factorielle)2013-2014 Algorithmique4
Un peu de vocabulaire
Pour une fonction récursive, on
parlera :•De récursivité terminale si aucune instruction n"est exécutée après l"appel de la fonction à elle-même •De récursivité non terminale dans l"autre cas2013-2014 Algorithmique5
ExempleTerminale
void f( int n){ if (n==0) System. out .println( "Hello" else f(n-1);Non terminale
void f( int n) { if (n>0) f(n-1);System.
out .println( "Hello"Récursivité directe
Lorsque fs"appelle elle-même,
on parle de récursivité directeLorsque fappelle gqui appelle f,
il s"agit aussi de récursivité•On l"appelle alors indirecte2013-2014 Algorithmique7
Exemples de structures
récursivesListe récursive•Le premier élément•Et le reste de la liste (qui est aussi une liste)
Une expression arithmétique est :•Soit une valeur•Soit une expression, un opérateur et une autre expression
2013-2014 Algorithmique8
Implémentation
Comment programmer une
fonction récursive ?Quels sont les pièges à éviter ?
2013-2014 Algorithmique9
Programmer une fonction
récursiveIl suffit de la faire s"appeler elle-mêmeint
f( int n){ return f(n-1);La fonction fest récursive : elle
s"appelle elle-mêmeMais fn"a-t-elle pas un problème ?2013-2014 Algorithmique10
Une obbligation : s"arrêter
La fonction ftelle qu"elle est écrite ne
s"arrête pas :•Appel : f(2) •Appel : f(1) •Appel : f(0) •Appel : f(-1) •Appel : f(-2) •Etc...2013-2014 Algorithmique11
Comment y parvenir
Première étape : la condition
terminale•Obligatoirement au début de toute fonction récursive•Une condition : le cas particulier•Pour ce cas, pas d"autre appel à la fonction : la chaîne d"appels s"arrête
2013-2014 Algorithmique12
Exemple
void f( int n){ if (n==0)System.
out .println( "Hello" else f(n-1); Ici quand nvaut 0, on s"arrêteProblème : arrive-t-on à n = 0 ?2013-2014 Algorithmique13
Terminaisonde la fonction
Il faut que la fonction s"arrêteLa condition terminale ne sert à rien si elle ne devient jamais vraieExemple avec la fonction précédente :•f(-2) provoque une pile d"appels infinie •Probablement d"autres tests à faire (si n<0, envoyer une exception par exemple)2013-2014 Algorithmique14
Une bonne solution
void f( int n) { if (n<0) System.exit(-1); if (n==0)System.
out .println( "Hello" else f(n-1);2013-2014 Algorithmique15
Pourquoi ça marche ?
Si nest négatif : on s"arrête sur une exceptionSi nest nul : c"est le cas d"arrêt (" Hello »)Si nest positif : on appelle favec 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 Algorithmique16
Il n"existe pas de moyen
automatique pour savoir si un programme termine ou pas2013-2014
Algorithmique17
Conclusion
Il faut regarder cas par cas, et
à la mainMême si aucune méthode n"est
générale, le principe de récurrence aide souvent2013-2014 Algorithmique18
En résumé
Une fonction récursive doit comporter :•Un cas d"arrêt dans lequel aucun autre appel n"est effectué•Un cas général dans lequel un ou plusieurs autres appels sont effectués
La chaîne d"appel doit conduire au critère d"arrêt•Optionnellement, des cas impossibles ou incorrects à traiter par des exceptions
2013-2014 Algorithmique19
Quelques exemples
Récursificationfacile ;
récursivité obligatoire ?2013-2014 Algorithmique20
Les boucles for
Très bonne candidateToute boucle forpeut se transformeren une fonction récursivePrincipe :•Pour faire des choses pour un indice allant de 1 à n•On les fait de 1 à n-1 (même traitement avec
une donnée différente)•Puis on les fait pour l"indice n(cas particulier)2013-2014 Algorithmique21
Traduction
void f( int n) { for (int i=0; i<=n; i++) traiter(i); void f( int n){ if (n==0) traiter(0); else f(n-1); traiter(n);Exemple : fonction factorielle
int fact( int n) { int res = 1; for (int i=1; i<=n; i++) res = res*i; return res; int fact( int n){ if (n==0)return 1; else returnfact(n-1)*n;2013-2014 Algorithmique23
Appel de fact(5)récursif
Phase de descente récursiveAppel à
fact(5)Appel à
fact(4)Appel à fact(3)Appel à fact(2)Appel à fact(1)Appel à fact(0)Condition terminale•
Retour de la valeur 1
2013-2014 Algorithmique24
SuitePhase de remontée
(après l"appel à fact(n-1) on multiplie par n: la récursivité n"est pas terminale)Retour de la valeur 1
Retour de la valeur
2Retour de la valeur
6Retour de la valeur
24Retour de la valeur
1202013-2014 Algorithmique25
Quelques conséquences
La plupart des traitement sur les
tableaux peuvent se mettre sous formerécursive :•Tris (sélection, insertion)•Recherche séquentielle (attention: pas dichotomique)•Inversion•Problème des huit reines•Etc...
2013-2014 Algorithmique26
Une constatation
L"écriture sous forme récursive est
toujours plus simple que l"écriture sousquotesdbs_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