Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Comprendre la récursivité Les équations sur ctte page sont affichées à l'aide d

Comprendre la récursivité Les équations sur ctte page sont affichées à l'aide de MathJax. Il y a des sujets qui, pour d'étranges raisons, font plus peur que d'autres. Les pointeurs, par exemple, ou encore le polymorphisme, qui sont des exemples classiques de concepts essentiels en informatique et qui semblent entourés d'une aura de crainte, crainte somme toute peu justifiée. Le présent document s'intéressera à l'un de ces sujets à haute teneur en crainte : la récursivité. Un exemple simple... presque simpliste Imaginons que nous ayons le mandat suivant : Écrire une fonction somme_un_a(n) qui prenne en paramètre un entier n et qui retourne la somme de1 à n inclusivement. Nous adopterons la convention que la fonction doive retourner 0 si n≤0 pour que le tout soit simple, et nous présumerons qu'aucun débordement ne se produira en cours de route, toujours dans l'optique de garder le propos aussi simple que possible. Notez que j'utilise (i..j) pour décrire l'intervalle discret fermé allant inclusivement de i à j. L'écriture (i..j( est pour moi ce qu'on appelle un intervalle à demi-ouvert, où i est inclus et j est exclu. La plupart des informaticiennes et des informaticiens auront sans doute le réflexe de résoudre ce problème à l'aide d'une répétitive, ce qui est une stratégie très raisonnable : Avec répétitive pour long somme_un_a(int n) { long cumul = {}; for (int i = 1; i <= n; i++) cumul += i; return cumul; } Avec répétitive tant que long somme_un_a(int n) { long cumul = {}; int i = 1; while (i <= n) { cumul += i; i++; } return cumul; } On pourrait aussi définir cette fonction de la manière suivante : Récursivité : définir la fonction... en fonction d'elle-même long somme_un_a(int n) { if (n <= 0) return 0L; else return n + somme_un_a(n-1); } Les versions avec répétitives sont plus efficaces dans ce cas-ci, mais la version où la fonction résout le problème en se rappelant elle-même a le mérite d'être très simple : On définit un cas d'arrêt: la somme de 1 à zéro ou moins est zéro, ce que nous savons de par la définition du problème donnée plus haut. Simple, efficace, sans équivoque et – surtout – sans récursivité, et On définit un ou plusieurs cas généraux qui s'expriment par une simplification du problème original : ici, ∑1n (présumant n>0) vaut n+∑1n−1 ) La stratégie d'ensemble d'une fonction récursive y est claire : Règle générale, on essaie d'exprimer la solution à un problème en fonction de lui même, mais en le simplifiant de manière à ce que, à chaque étape, on converge de plus en plus vers un cas trivial (plus haut, le cas où n≤0), et On définit un cas banal qui sera éventuellement atteint et pour lequel la réponse est connue. Sans un tel cas, la récursivité procédera ad infinitum et nous n'aurons pas de solution au problème attaqué Celles ou ceux parmi vous qui sont familières ou familiers avec les techniques de preuve mathématique reconnaîtront peut-être dans la récursivité des similitudes avec la technique de preuve par induction. Les fonctions récursives sont l'enfant chéri des mathématicien(ne)s; il est fréquent que des structures mathématiques soient définies de manière récursive, ce qui est compréhensible: règle générale, une stratégie récursive s'exprime de manière simple, élégante et compacte. Un cas célèbre est la définition des entiers naturels, donnée par Giuseppe Peano, qui décrit les entiers à partir d'un entier de base (zéro) et de l'opération successeur (écrite succ(), à droite). Dans ce modèle, donc, écrire 2 est un raccourci pour écrire successeur de (successeur de (0))). L'un des points où l'informatique se distingue fréquemment de la mathématique est le souci de trouver non seulement une solution à un problème, mais aussi une solution efficace. En effet, si exprimer la somme de (1..n) de manière récursive est élégant et compact, c'est aussi une stratégie très inefficace (ne généralisons toutefois pas le cas à toutes les stratégies récursives: il y a des cas où une approche récursive constitue véritablement la stratégie à adopter; le truc est de choisir ses combats et de choisir les armes les plus efficaces pour faire face à chaque adversaire). succ(0) == 1 succ(1) == succ(succ(0)) == 2 ... succ(n) == succ(succ(n-1)) On peut tracer rapidement ce que cette stratégie donnerait pour n=5 lors de l'invocation initiale de somme_un_a() : somme_un_a(5) == 5 + somme_un_a(4) == 5 + (4 + somme_un_a(3)) == 5 + (4 + (3 + somme_un_a(2))) == 5 + (4 + (3 + (2 + somme_un_a(1)))) == 5 + (4 + (3 + (2 + (1 + somme_un_a(0))))) == 5 + (4 + (3 + (2 + (1 + (0))))) == 5 + (4 + (3 + (2 + (1)))) == 5 + (4 + (3 + (3))) == 5 + (4 + (6)) == 5 + (10) == 15 Certaines outils, en particulier ceux pensés pour les langages fonctionnels, tendent à optimiser les expressions récursives quand la récursivité apparaît à la toute fin, ce qu'on appelle de la Tail Recursion. Pour une explication de cette mécanique, voir http://rodrigosasaki.com/2012/11/24/tail-recursion/. Remarquez que la solution du problème résulte d'un cumul de données. La stratégie récursive repousse à la toute fin de la récursion la tâche de mettre ensemble les petits morceaux de calculs trouvés en chemin. Cela a pour effet qu'une fonction récursive requiert, en général, des ressources cumulatives pour en arriver à un résultat, quand bien même ce ne serait que pour gérer les appels à la fonction récursive qui s'empilent jusqu'à obtention d'un résultat: somme_un_a(5) ne peut se compléter sans avoir obtenu le résultat de somme_un_a(4), qui dépend du résultat de somme_un_a(3), et ainsi de suite, ce qui fait en sorte que somme_un_a(n) entraînera, au pire moment, n (en fait, n+1, mais cela importe peu) appels empilés à somme_un_a(). Chaque appel entraîne l'utilisation d'espace pour les états intermédiaires (valeur de retour, variables locales, etc.) ce qui peut devenir très, très coûteux : Dans le schéma qui précède, en forme de pyramide, le pic de la pyramide représente le moment où on a atteint le coût maximal en ressources pour un appel original à somme_un_a(5). On imagine bien le coût de somme_un_a(10000), surtout en comparaison avec une stratégie itérative qui ne ferait que 10000 itérations dans une répétitive et qui, en ne se rappelant pas, ne nécessiterait qu'un seul appel à la fonction somme_un_a(). On prétend (est-ce une légende urbaine?) que Carl Friedrich Gauss, un très grand mathématicien (certains l'ont qualifié de Prince des mathématiciens), était un élève turbulent à la petite école, et que son maître lui avait accolé le problème de calculer la somme des entiers situés inclusivement entre 1 et 100, pensant ainsi le tenir occupé. Selon la légende, il aurait très rapidement répondu correctement (5050), ayant remarqué que, si on aligne les entiers à additionner côte à côte, on obtient : 1+2+3+…+98+99+100 qu'on peut grouper par paires comme suit : (1+100)+(2+99)+(3+98)+… de manière à ce que la valeur dans chaque parenthèse soit la même (101), et qu'il y ait (1002, donc 50) parenthèses. Le reste est affaire de multiplication élémentaire, qui se généralise simplement : long somme_un_a(int n) { long cumul = {}; if (n > 0) if (n % 2 == 0) // n pair cumul = (1 + n) * (n / 2); else cumul = n + (1 + (n - 1)) * ((n-1) / 2); return cumul; } ce qui est, en soi, une définition récursive : long somme_un_a(int n) { if (n <= 0) return 0L; else if (n % 2 == 0) // n pair return (1 + n) * (n / 2); else return n + somme_un_a(n-1); } mais seulement par la bande. En fait, cette stratégie demande un temps constant à appliquer, peu importe la valeur originale de n, alors que les stratégies itératives et récursive proposées plus haut demandent un temps linéaire (le temps requis pour traiter le problème croît de manière proportionnelle à la valeur de n). Ici, une analyse mathématique – même simple – comme celle faite par Gauss représente un gain considérable de qualité. Cas où la stratégie récursive est avantageuse Imaginons que nous ayons le mandat suivant : Écrire une fonction puissance(base,exp) qui prenne en paramètre deux entiers, base et exp. Pour simplifier le propos, nous présumerons base > 0, exp >= 0 et nous présumerons que baseexp ne provoque aucun débordement de capacité (pour voir comment on pourrait garantir le respect des contraintes base > 0 et exp >= 0 à coût presque zéro, voir cet encadré). Ici encore. une solution répétitive est très accessible – il s'agit même d'un problème fréquemment servi à des étudiant(e)s inscrit(e)s dans un cours de base de programmation : Avec répétitive pour long puissance(int base, int exp) { long cumul = 1L; for (int i = 0; i < exp; ++i) cumul *= base; return cumul; } Avec répétitive tant que long puissance(int base, int exp) { long cumul = 1L; int cpt = 0; while (cpt < exp) { cumul uploads/Management/ comprendre-la-r-wps-office 1 .pdf