Outils d'utilisateurs
recursivite
Différences
Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.
|
recursivite [2016/12/05 02:27] gbdivers |
recursivite [2016/12/06 02:41] (Version actuelle) gbdivers |
||
|---|---|---|---|
| Ligne 3: | Ligne 3: | ||
| - | ====== Les fonctions recursives ====== | + | ====== Les fonctions récursives ====== |
| Une fonction récursive est une fonction qui s'appelle elle-même. Cela est donc équivalent aux boucles et permettent de répéter une suite d'instructions. | Une fonction récursive est une fonction qui s'appelle elle-même. Cela est donc équivalent aux boucles et permettent de répéter une suite d'instructions. | ||
| Ligne 18: | Ligne 18: | ||
| <code cpp> | <code cpp> | ||
| - | void g(); // declaration anticipee | + | void g(); // déclaration anticipée |
| void f() { | void f() { | ||
| Ligne 31: | Ligne 31: | ||
| Dans ce code, la fonction ''f'' appelle la fonction ''g'', qui appelle la fonction ''f'', qui appelle la fonction ''g'', et ainsi de suite. | Dans ce code, la fonction ''f'' appelle la fonction ''g'', qui appelle la fonction ''f'', qui appelle la fonction ''g'', et ainsi de suite. | ||
| - | <note>**Declaration anticipee** | + | <note>**Déclaration anticipée** |
| Si vous lisez le code ligne par ligne, comme le fait le compilateur, vous remarquez que dans la fonction ''f'', la fonction ''g'' n'est pas encore connue par le compilateur. Vous aurez donc un message d'erreur "g n'est pas déclarée" : | Si vous lisez le code ligne par ligne, comme le fait le compilateur, vous remarquez que dans la fonction ''f'', la fonction ''g'' n'est pas encore connue par le compilateur. Vous aurez donc un message d'erreur "g n'est pas déclarée" : | ||
| Ligne 55: | Ligne 55: | ||
| </note> | </note> | ||
| - | ===== Condition d'arret et continuation ===== | ||
| + | ===== Condition d’arrêt et continuation ===== | ||
| Comme pour les boucles classiques, il est important de faire attention aux conditions d'arrêt, pour éviter les boucles infinies. Dans les codes précédents, il n'y a pas de condition d'arrêt, ce qui implique que ces boucles tourneront à l'infini, jusqu'à ce que le programme plante. | Comme pour les boucles classiques, il est important de faire attention aux conditions d'arrêt, pour éviter les boucles infinies. Dans les codes précédents, il n'y a pas de condition d'arrêt, ce qui implique que ces boucles tourneront à l'infini, jusqu'à ce que le programme plante. | ||
| Ligne 89: | Ligne 89: | ||
| Dans ce code, lorsque la condition est vraie, la fonction ''f'' est appelée récursivement. Dans le cas contraire, la fonction s'arrête. | Dans ce code, lorsque la condition est vraie, la fonction ''f'' est appelée récursivement. Dans le cas contraire, la fonction s'arrête. | ||
| + | Ce type d'approche est régulièrement utilisé en informatique, puisque bien adaptée pour certains types de problèmes : la recherche et le tri de collection par exemple. | ||
| - | ===== Complexite et limitation ===== | + | Ce principe de récursivité peut être étendu également aux structures de données. Il existe en effet des structures de données conçues de façon récursives et l'utilisation d'algorithmes récursifs est particulièrement adapté dans ce cas. Un exemple que vous connaissez déjà est la collection associative ''std::map'', qui utilise en interne un structure en arbre. (Les structures de données récursives seront étudiées dans la partie sur la programmation orientée objet). |
| - | Selon la complexité des algorithmes, il n'est pas toujours simple de garantir qu'un algorithme récursif se termine toujours correctement, quelques soit les conditions. La démonstration qu'un algorithme est correct peut être rapproché des raisonnement par récurrence en mathématique. | ||
| - | **performances** | + | ===== Problématiques ===== |
| + | |||
| + | La récursivité n'est pas une fonctionnalité triviale, il est important de bien comprendre les limitations avant de l'utiliser. | ||
| + | |||
| + | Pour commencer, selon la complexité des algorithmes, il n'est pas toujours simple de garantir qu'un algorithme récursif se termine correctement, quelques soit les conditions. Cela nécessite généralement plus de travail pour mettre en place un tel algorithme. La démonstration qu'un algorithme est correct peut être rapproché des raisonnement par récurrence en mathématique. | ||
| + | |||
| + | Le deuxième probleme est lié a la gestion des appels de fonction dans un ordinateur. Généralement, chaque appel de fonction sera ajouté à la Pile d'appel des fonctions : le contexte d’exécution de la fonction appelante sera sauvegardé et un nouveau contexte pour la fonction appelée est créé. Lorsqu'une fonction se termine, le contexte de la fonction appelée est détruit et le contexte de la fonction appelante est restauré. Tout cela est coûteux pour les performances (et un peu pour la mémoire). | ||
| + | |||
| + | Dans certaines conditions, le compilateur est capable de supprimer un appel de fonction, comme si il n'y avait pas d'appel de fonction du tout. Avec les fonctions récursives, cette optimisation est plus complexe pour le compilateur et il ne sera généralement pas capable de la faire. | ||
| + | |||
| + | Et ce n'est pas la seule optimisation que le compilateur sera incapable de faire. Plus généralement, le compilateur arrivera plus facilement à optimiser une boucle classique qu'un algorithme récursif. Par exemple pour dérouler une boucle (remplacer une boucle par une série d'instructions sans boucle) ou utiliser certaines fonctionnalités des processeurs (par exemple la parallélisation, pour exécuter plusieurs instructions en même temps). | ||
| + | |||
| + | Ces problématiques ne doivent pas vous empêcher d'utiliser la récursivité, mais simplement de bien faire attention avant de l'utiliser. | ||
| Ligne 129: | Ligne 141: | ||
| Dans ce code, la fonction ''f'' prend en paramètre un compteur entier. Ce paramètre est passé par valeur, ce qui signifie que la valeur sera copiée lors de chaque appel à la fonction ''f''. | Dans ce code, la fonction ''f'' prend en paramètre un compteur entier. Ce paramètre est passé par valeur, ce qui signifie que la valeur sera copiée lors de chaque appel à la fonction ''f''. | ||
| - | La valeur du compteur est affichée dans un premier temps avec ''std::cout''. Ensuite, cette valeur est testée : si elle est superieur à zéro, la fonction ''f'' est appelée récursivement. Dans le cas contraire, la fonction s'arrête. | + | La valeur du compteur est affichée dans un premier temps avec ''std::cout''. Ensuite, cette valeur est testée : si elle est supérieur à zéro, la fonction ''f'' est appelée récursivement. Dans le cas contraire, la fonction s'arrête. |
| - | Le point important à noter est que le compteur est décrémenté à chaque appel récursif à la fonction ''f''. Pour bien comprendre ce qui se passe, il faut "dérouler" la boucle : | + | Le point important à noter est que le compteur est décrémenté à chaque appel récursif à la fonction ''f''. Pour bien comprendre ce qui se passe, il faut "dérouler" manuellement la boucle : |
| * la fonction ''main'' appelle la fonction ''f'' avec la valeur ''5'' en argument ; | * la fonction ''main'' appelle la fonction ''f'' avec la valeur ''5'' en argument ; | ||
| Ligne 144: | Ligne 156: | ||
| ===== Diviser pour régner ===== | ===== Diviser pour régner ===== | ||
| - | https://fr.wikipedia.org/wiki/Diviser_pour_r%C3%A9gner_(informatique) | + | "Diviser pour régner" (//divide and conquer// en anglais) est une stratégie de résolution de problématiques, basée sur la récursivité. Le principe générale consiste à prendre un problème complexe et de le diviser en sous-problèmes moins complexes. Puis de diviser encore ces sous-problèmes en sous-problèmes moins complexes, et ainsi de suite, jusqu'à obtenir des problèmes simples à résoudre. |
| - | divide and conquer en anglais | + | Cette stratégie n'est pas spécifique à la programmation et il est assez facile de trouver un exemple dans la vie de tous les jours pour illustrer ce principe. |
| - | grande classe de resolution de problemes via recurision. Idee : diviser en sous preobleme, resoudre les sous probleme, combiner les resultat. | + | Imaginez par exemple que vous êtes chef de la police d'une ville et que vous devez trouver un voleur qui se cache dans votre ville. Vous ne savez pour où il est, mais vous savez qu'il est dans la ville. Vous n'allez pas fouiller toutes les maisons vous-même, il vous faut de l'aide. Et vous ne pouvez pas simplement dire à vos policiers de fouiller les maisons au hasard, sinon certaines maisons seront fouillées deux fois et d'autres maisons ne seront pas fouillées : il vous faut vous organiser. |
| - | Exemple concret : vous avez une pile de feuilles, que vous devez relire et corriger les fautes d'orthographe. Pour proceder : | + | Vous allez commencer par diviser la ville en secteurs de recherche, par exemple par quartier. Et vous allez donner la responsabilité de fouiller chaque quartier à un inspecteur de police. Vous êtes donc sur que tous les quartiers seront fouillées une et une seule fois. |
| - | * vous diviser le paquet en 2 | + | De la même façon, chaque inspecteur ne va pas fouiller chaque maison tout seul. Il va diviser sa zone de recherche en secteurs, par exemple par rues. Il va donc assigner un sergent de police à chaque rue, ce qui lui donne la garantie que toutes les rues seront fouillées et qu'aucune ne sera oubliée. |
| - | * vous donner la moitiee a une autre personne, pour qu'elle corrige la moitie et vous vous occuper de l'autre moitie | + | |
| - | * vous divisez encore en 2 le paquet qu'il vous reste et vous donner la moitie a une troisieme personne. La deuxieme personne fait la meme chose et donne la moitie de son paquet a une quatrieme personne ; | + | Pour terminer, chaque sergent va procéder de la même manière et va diviser la rue en zones de recherche plus petites : les maisons. |
| - | * vous recommancez : chacun divise son paquet en 2 et donne la moitie a 4 autres personnes | + | |
| - | * et ainsi de suite, jusqu'a temps que vous n'ayez pas trop de pages a corriger. | + | Cette division du travail complexe (fouiller une ville) en tâches de plus en plus simples (fouiller les quartiers, les rues puis les maisons) facilite l'organisation du travail et est assez naturelle à mettre en place pour cette problématique. |
| + | |||
| + | Un pseudo-code C++ équivalent pourrait ressembler au code suivant : | ||
| + | |||
| + | <code cpp> | ||
| + | void fouiller(ZoneGéographique zone) { | ||
| + | std::vector<ZoneGéographique > sousZones = diviser(zone); | ||
| + | for (auto sousZone: sousZones) { | ||
| + | fouiller(sousZone); // récursion | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | ZoneGéographique ma_ville; | ||
| + | fouiller(ma_ville); | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | Ce code est quasiment une transcription littérale de la procédure précédente, il est assez simple de comprendre le principe. | ||
| + | |||
| + | |||
| + | ===== Transformation en itération ===== | ||
| + | |||
| + | Comme expliqué au début de ce chapitre, les algorithmes récursifs peuvent être assimilés à des boucles. Il est donc naturel de se poser la question de savoir s'il est possible de transformer un algorithme récursif en algorithme itératif (utilisant une boucle classique). | ||
| + | |||
| + | Avec l'exemple précédent de la fouille d'une ville, il est possible de répartir le travail entre les policiers de façon différente. Il est par exemple possible de compter le nombre de rues dans la ville et le nombre de policiers disponibles, puis de calculer le nombre moyen de policiers par rue. Il est alors facile d'assigner les policiers pour chaque rue, avec une boucle classique. | ||
| + | |||
| + | Le pseudo-code C++ devient donc : | ||
| + | |||
| + | <code cpp>; | ||
| + | int main() { | ||
| + | ZoneGéographique ma_ville; | ||
| + | |||
| + | int nombreRues = compterRues(ma_ville); | ||
| + | int nombrepoliciers = compterPoliciers(ma_ville); | ||
| + | |||
| + | int tailleGroupes = nombrepoliciers / nombreRues; | ||
| + | std::vector<Groupe> groupesPoliciers = créerGroupesPoliciers(tailleGroupes); | ||
| + | |||
| + | for (auto groupePolicier: groupesPoliciers) { | ||
| + | fouiller(groupePolicier, rue); | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| - | Exemples : recherche, tri, arbres, | + | Dans ce code, la fonction récursive est remplacée par une boucle ''for''. |
| - | Note : principe application aussi aux structures de donnees. Par exemple, au lieu d'avoir un vector de N elements, vous pouvez avoir 2 vector de N/2 elements. Ou 4 vectors de N/4 elements, etc. | + | Malgré le fait qu'il est possible de transformer une récursion en itération, cela ne retire par l'intérêt de la récursion dans certains. Il est possible d'imaginer que le nombre de maisons dans la ville ne soit pas le même dans chaque rue. Avec la réparation décrite ci-dessus, cela implique qu'il y aura autant de policiers dans une rue qui contient 10 maisons, qu'une rue qui en contient 100 : la réparation du travail n'est pas optimale. |
| - | Ces structures de donnees "recursives" presentent des avantages tres interessants pour certaines problematiques (std::map utilise par exemple en interne ce type de structure de donnees). Et les algorithmes recurisves sont donc en toute logique particulierement adpatee pour travailler sur de telles structures. | + | Dans la récursion, il est possible d'évaluer lors de chaque appel s'il reste beaucoup de travail à réaliser et choisir s'il est intéressant de continuer ou non la récursion. |
| - | arbres, graph, etc. | ||
recursivite.1480901242.txt.gz · Dernière modification: 2016/12/05 02:27 par gbdivers
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Noncommercial-Share Alike 3.0 Unported
