La Récursivité

La Récursivité

> Tutoriel LeekScript

Prérequis:

----

La récursivité, de manière générale, est la capacité d'un objet à faire référence à lui-même. Dans le monde réel, cela se manifeste de la manière la plus évidente par les fractals, ainsi que lorsque l'on met face a face deux miroirs. On retrouve aussi cette notion dans les phrases du style: "Je rêve que je rêve que je rêve." ou bien "Je pense que j'écris que je rêve que je pense que j'écris...", etc. En programmation, cela se manifeste principalement avec les fonctions qui s’appellent elles-mêmes:

function loop() { loop(); }

La fonction ci-dessus est la fonction récursive la plus simple qui puisse être. Lorsque appelé, elle ne fait rien sinon s'appeler elle-même. Cela revient au même que d'utiliser une boucle infini (eg. while(true);). Nous nous servirons de cette fonction comme squelette de base pour toutes nos future fonctions récursives.

Récursion

La récursion est analogue à de la déconstruction. On la retrouve principalement dans les algorithmes de type ''Diviser pour Régner''. Pour résoudre notre problème, on commence par le subdiviser en sous-problèmes plus simples à résoudre, on répète le processus jusqu'à trouver un problème que l'on sait résoudre directement, et à partir de là, on résout les problèmes supérieur en combinant nos solutions précédentes.

Définir la Somme de 0 à n

On veut définir une fonction prenant en paramètre un nombre entier n et retournant la somme de 0 à n (eg. 0 + 1 + ... + n). Reprenant notre squelette de base, on peut commencer avec la fonction suivante:

function sumN(n) { sumN(?); return ?; }

Pour l'instant, nous avons les informations suivantes:

Lorsque nous travaillons en récursivité, il est toujours une bonne idée de commencer par la condition d'arrêt. Dans le cas de la récursion, nous voulons nous arrêter de créer des sous-problèmes lorsque nous avons trouvé quelque chose que nous pouvons résoudre. En l’occurrence, la somme de 0 à 0 est quelque chose que nous savons résoudre. 0 est donc notre cas de base, nous pouvons directement retourner la somme correspondante.

function sumN(n) { if (n === 0) { return 0; } else { sumN(?); return ?; } }

Il nous faut maintenant trouver comment atteindre le cas de base. Nous pourrions soustraire n à lui-même, mais dans ce cas, il nous serait impossible de faire la somme des entiers entre 0 et n, nous n'aurions que 0 et n à disposition. Il va donc nous falloir créer un sous-problème qui puissent résoudre une somme avec un n plus proche de notre cas de base.

function sumN(n) { if (n === 0) { return 0; } else { sumN(n - 1); return ?; } }

Il ne nous manque plus qu'à actuellement faire la somme, ce qui nous étais demandé au début. Ici, la somme de 0 à n c'est aussi la somme de la somme de 0 à n - 1 et n.

function sumN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }

Avec un ternaire:

function sumN(n) { return n === 0 ? 0 : n + sumN(n - 1); }

N'hésitez pas à essayer le code dans votre éditeur Leekwars. Peut-être découvrirez-vous le principal problème de la récursivité. Vous pouvez aussi visualiser l'exécution (de manière basique) sur ce site ou utiliser cette librairie de Hazurl pour le débogage des fonctions récursives.

Corécursion

/!\ Section a refaire, ce qui est montré est principalement de la récursion terminale. Inadapté à plusieurs embranchements. /!\ La corécursion est analogue à de la construction. Contrairement à la récursion où nous cherchions à atteindre un cas de base à partir de notre problème principal, en corécursion, nous commençons directement avec notre cas de base, et nous avançons vers la solution du problème principal.

Récursion Mutuelle

Nous avons déjà abordé la récursion mutuelle avec les miroirs et les phrases. En programmation, avec les fonctions, cela se traduit par deux ou plus fonctions qui s'appellent entre elles. Nous présentons ci-dessous le cas le plus simple de récursion mutuelle:

function mutualLoop() { mutualHelper(); }

function mutualHelper() { mutualLoop(); }

Pas véritablement plus compliqué que la récursion simple, mais rarement plus utile avec les fonctions, cette forme de récursion montre tout son intérêt lorsque le langage utilisé offre la possibilité de définir des structures de données récursive. Cependant nous n'aborderont pas ce sujet à moins que Leekscript 2 viennent à obtenir cette capacité (probablement déjà possible bien que relativement impropre) ou que les lecteurs en fasse la requête.

Définir isOdd et isEven

On souhaite ici définir deux fonctions: isOdd prends un entier naturel et retourne si ce nombre est impair ou non, isEven prends un entier naturel et retourne si ce nombre est pair ou non. Nous allons aussi appliquer les restrictions suivantes:

Comme d'habitude, nous commençons par réutiliser le squelette de base:

Le cas de base, 0 pour les entiers naturels:

function isOdd(n) { if (n === 0) { return false; } else { isEven(?); return ?; } }

function isEven(n) { if (n === 0) { return true; } else { isOdd(?); return ?; } }

On s'approche du cas de base:

Il ne nous reste plus qu'à déterminer comment utiliser le retour d'isEven et isOdd. En supposant que n = 1, dans le cas d'isOdd, isEven nous retourneras true car 1 - 1 = 0, nous pouvons donc retourner la même valeur; dans le cas d'isEven, isOdd nous retourneras false car 1 - 1 = 0, à nouveau, nous pouvons nous permettre de retourner la même valeur. Nous obtenons ainsi les fonctions suivantes:

function isOdd(n) { if (n === 0) { return false; } else { return isEven(n - 1); } }

function isEven(n) { if (n === 0) { return true; } else { return isOdd(n - 1); } }

Comme toujours, n'hésitez pas à vérifier avec votre éditeur. Essayez-vous aussi à les réécrire avec des ternaires, et pourquoi pas de manière corécursive, toute pratique est bonne pour vous faire la main. Attention à ne pas vous compliquer la tâche inutilement.

Exercices

Vitef.

Définir la fonction factorielle de manière récursive.

factorial 0 = 1 factorial n = n * (n - 1) * ... * 1

Définir la fonction fibonacci de manière récursive.

fibonacci 0 = 1 fibonacci 1 = 1 fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

Il est possible d'écrire isOdd et isEven avec de la récursion simple. En conservant les mêmes restrictions, réécrivez ces deux fonctions de manière récursive.

Débordement de la Pile d'Exécution

Ou autrement appelé Stack Overflow. Faire des appels de fonction ça n'est pas gratuit. Le processeur à besoin d'un espace de travail pour stocker les arguments de la fonction et ses variables locales. Cet espace est conservé tant que la fonction n'a pas retourné de valeur. Lorsque une fonction appel une fonction, un nouvel espace de travail est généré pour cette dernière. Mais l'ancien reste, car la première fonction n'a pas encore pu retourner de valeur. Lorsque nous appelons la fonction loop, nous générons une infinité d'espaces de travail. Et même si loop n'a ni argument, ni variable locale, elle a tout de même besoin de s'appeler. Cela veut dire qu'elle a besoin d'un peu de place pour faire cet appel. Et une infinité de petit peu, ça fait vraiment beaucoup. Tellement même qu'aucun ordinateur au monde ne peut empiler la totalité des espaces de travail nécessaire à l’exécution de loop. Afin d'éviter d'avoir ''trop'' de problème de débordement de la pile d'exécution, certain langages impose une limite à la profondeur d'appel récursif possible. C'est le cas de Leekscript. Si vous avez lu le didacticiel disponible sur le site officiel, vous aurez peut-être remarqué qu'il était annoncé une limite de 200 appel. Cette valeur n'est plus d'actualité, mais par principe cela veut dire que lors du 201ème appel à loop l’interprète Leekscript arrêterait votre script, et annoncerais un plantage avec pour erreur un ''stack overflow''. A l'heure de l'écriture de cette article, l'auteur estime que l'interprète Leekscript se base sur une taille maximal de pile d'exécution. Toutes les fonctions n'ont pas besoin de la même taille d'espace de travail. Avoir une fonction très légère devrait pouvoir se répéter plus de fois sur un ordinateur donné qu'une fonction lourde. Avoir une limite basé sur la taille de l'espace de travail du programme plutôt que sur une profondeur arbitraire qui risquerait de restreindre inutilement certains codes semble plus intéressant pour l'utilisateur du langage.

Appel Terminal

Cette notion n'est pas exclusive à la récursion, mais elle à vue son apparition grâce au problème de débordement de la pile d'exécution. Nous avons vu que l'espace de travail d'une fonction ne disparaissait pas tant qu'aucune valeur n'était retournée. Si nous observons la définition récursive de sumN, il est aisé de comprendre pourquoi. Lorsque nous faisons un appel interne à sumN, il nous reste encore une addition à effectuer avant de pouvoir retourner un résultat. Cependant, si nous faisions l'addition avant notre appel, il n'y aurait pas besoin d'effectuer de travail supplémentaire. Certain langages, dont Leekscript ne fais pas partie à l'heure de l'écriture de cette section, effectue une optimisation appelé ''élimination d'appel terminal'' qui consiste à détruire (ou réutiliser) l'espace de travail de la fonction appelante et le remplacer par celui de la fonction appelée lorsque la première se contente de retourner le résultat de la deuxième. Prenons le cas de la fonction loop. Lorsque appelée, la seule chose qu'elle fait est se rappeler elle même. (Elle ne fait pas de retour, mais elle ne fait pas plus de travail derrière non plus.) Cela veut dire qu'avec l'élimination de son espace de travail à chaque sous appel, au lieu d'avoir un programme qui utilise un espace de travail infiniment grand, nous aurions un programme avec un espace de travail qui reste minime, même il ne s'arrêtera jamais.

Définir la Somme de 0 à n

A nouveau, en réutilisant notre squelette de fonction:

function tailSumN(n) { tailSumN(?); return ?; }

Contrairement à précédemment, nous possédons moins d'informations utiles qu'avant:

Nous sommes presque exactement dans la même situation qu'avant, et si nous répétons le même processus qu'avant, nous aurons le même résultat qu'avant.

La modification la plus simple à apporter est de retourner directement le résultat:

function tailSumN(n) { return tailSumN(?); }

Il nous faut aussi décider d'où placer l'addition. Nous ne pouvons utiliser le résultat de tailSumN, il nous faut donc le faire avant l'appel: dans une variable avant l'appel, ou directement en argument de l'appel:

function tailSumN(n) { return tailSumN(? + ?); }

Nous pourrions utiliser n en tant qu'opérande pour notre addition, mais il nous faut aussi considérer la condition d'arrêt. Dans les deux cas, nous avons besoin de deux nouvelles valeurs. Soit un cas de base et une part de l'addition, soit deux parts de l'addition. Nous garderons n pour notre condition d'arrêt. Cela veut dire que nous aurons une valeur à comparer avec, et que cette valeur devra tendre vers n. Ce sera donc la partie qui est ajouté à la somme (x), et l'autre valeur est donc la somme jusqu'à maintenant (acc).

function tailSumN(n, x, acc) { if (? === n) { return ?; } else { return tailSumN(n, ? , x + acc); } }

Assez facilement, on peut déduire que x sera comparé à n. De même, x étant la partie modifié à chaque étape de l'addition, et sachant que 0 et que x tend vers n, nous avons simplement à ajouter 1 pour nous rapprocher de n.

function tailSumN(n, x, acc) { if (x == n) { return ?; } else { return tailSumN(n, x + 1, acc + x); } }

Il nous reste à décider de ce qu'il faut retourner lorsque notre condition d'arrêt est satisfaite. n nous sert seulement à contrôler notre somme, nous ne l'utiliserons donc pas. x seul n'à pas de sens puisque la somme des étapes précédentes est contenu dans acc. Nous avons deux possibilité: soit acc seul, soit acc + x. Pour choisir entre les deux, nous pouvons comparer les résultats de l'application des deux possibilités d'abord avec:

Nous pouvons voir assez rapidement que le résultat attendu est donné par acc + x.

function tailSumN(n, x, acc) { if (x == n) { return acc + x; } else { return tailSumN(n, x + 1, acc + x); } }

Il est possible d'utiliser acc seul en retour final en utilisant x = 1 pour l'appel initial, mais le choix effectué ici permet de rendre les deux branches de la fonction plus similaire. Dans les deux cas, nous effectuons une addition, mais lorsque la condition d'arrêt est satisfaite, nous ne rappelons pas tailSumN.

Utiliser cette fonction requiert que l'utilisateur sache comment tailSumN fonctionne. Elle a besoin d'un n, du cas de base, et d'un accumulateur. Hors nous souhaitons simplement obtenir la somme de 0 à n. Il nous faut donc définir une fonction intermédiaire qui s'occupera d'appeler tailSumN avec les bons arguments.

function sumN(n) { return tailSumN(n, 0, 0); }

function tailSumN(n, x, acc) { if (x === n) { return acc + x; } else { return tailSumN(n, x + 1, acc + x); } }

L'utilisateur peut maintenant appeler sumN sans se poser plus de question. Allez-y, n'hésitez pas à essayer dans votre éditeur Leekwars, ou observer sur ce site. En utilisant une ternaire et une closure:

function sumN(n) { var go = function(x, acc) { return x === n ? x + acc : go(x + 1, acc + x); }; return go(0, 0); }

Pour information, go est appelée une fonction aide (helper function ou helper en anglais).

Il est parfois possible d'utiliser le ou les arguments d'origine (ici n) pour atteindre la condition d'arrêt. Je vous invite donc à réécrire tailSumN sans l'intermédiaire x. Faites simple, inspirez vous de ce que vous connaissez déjà.

Exercices

Reprenez les fonctions des exercices précédents et réécrivez les avec de la récursion terminale.

Structures de Donnée Récursive

Liste

Une liste est défini comme étant soit une liste vide (généralement appelé Nil), soit un élément et le reste de la liste (sous forme de paire). En LS1, nous traduirons Nil par un tableau vide: [], et la paire par un tableau à deux éléments: [a, List a]. Ainsi, une liste contenant les éléments, 1, 2, 3, 4 se traduira par [1, [2, [3, [4, []]]]]. Nous définirons aussi quelques fonctions utiles à la manipulation de ce type de donnée:

function nil() { return []; } // () -> List a // Pour instancier une liste vide. function cons(x, xs) { return [x, xs]; } // (a, List a) -> List a // Pour ajouter un élément à une liste (comprendre créer une liste plus longue). function head(xs) { return xs[0]; } // List a -> List a // Pour récupérer la tête, crash si liste vide (retourne null en réalité). function tail(xs) { return xs[1]; } // List a -> List a // Pour récupérer la queue, même commentaire. function empty(xs) { return xs == nil(); } // List a -> Bool

Comme l'objectif de cet article est de travailler la récursivité, le code pour une fonction fromArray est donné directement:

function fromArray(xs) { return arrayFoldRight(xs, cons, nil()); }

Il est possible de la recoder de manière récursive, n'hésitez pas à le faire, vous pouvez comparer les résultat de votre implémentation avec celle ci-dessus.

Pour manipuler les éléments d'une liste, il nous faut la décomposer pour pouvoir travailler à l'élément de tête et plus tard le reste des éléments. Comme premier exercice, vous allez devoir implémenter une fonction récursive qui affiche les éléments de la liste en paramètre. Une première version les affichera dans l'ordre extérieur vers intérieur (pre order): 1, 2, 3, 4 -> 1 2 3 4, puis une deuxième version qui s'en occupe de l'intérieur vers l'extérieur (post order): 1, 2, 3, 4 -> 4 3 2 1. Nil ne sera pas affiché. Vous pouvez manipuler directement les tableaux, mais il est préférable d'utiliser les fonctions prévus à cet effet définies plus haut. Les variables sont inutiles, le mot clé var et l'opérateur d'assignation = ne devrait pas apparaître dans votre code.

Rappelez-vous, commencez d'abord par la condition d'arrêt. Ce type de donnée est très simple, il ne présente que deux cas possible, cela rends très simple la décision de quand arrêter la récursion.

Fonction squelette:

function printInOrder(xs) { /* code */ } // List a -> ()

printInOrder(fromArray([1, 2, 3, 4])); > [LeekySquash] 1 > [LeekySquash] 2 > [LeekySquash] 3 > [LeekySquash] 4

function printPostOrder(xs) { /* code */ } // List a -> ()

printPostOrder(fromArray([1, 2, 3, 4])); > [LeekySquash] 4 > [LeekySquash] 3 > [LeekySquash] 2 > [LeekySquash] 1

Maintenant que vous savez parcourir une liste et manipuler les éléments dans un ordre où dans l'autre. Vous allez implémenter une fonction toArray qui prend une liste en paramètre, et retourne un tableau avec les éléments dans le même ordre. Ainsi: [1, 2, 3, 4] == toArray(fromArray([1, 2, 3, 4])). Encore une fois, préférez utiliser les fonctions de manipulation de liste plutôt que manipuler directement les tableaux (hormis pour le tableau résultant bien entendu).

function toArray(xs) { /* code */ } // List a -> Array a

debug([1, 2, 3, 4] == toArray(fromArray([1, 2, 3, 4]))); > [LeekySquash] true

Plusieurs implémentations sont valide, mais la plus simple se réalise sans variable ni assignation.

Maintenant que vous avez de quoi afficher de manière compacte et lisible vos listes avec debug(toArray(xs)), vous allez pouvoir examiner plus facilement les résultats de vos fonctions.

Au cours de l'implémentation de toArray, il est possible que vous ayez à un moment ou un autre eu le tableau demandé à l'envers. L'exercice qui suit fera la même chose, mais avec une liste en résultat. Vous allez implémenter une fonction reverse qui prends une liste en paramètre et retourne une nouvelle liste avec les éléments ordonnés dans l'autre sens. (Cette fonction existe déjà pour les tableaux, mais personne ne s'en sert, donc n'hésitez pas à réutiliser le nom.) À nouveau, efforcez-vous de n'utiliser que les fonctions prévues pour plutôt que de toucher aux tableaux.

function reverse(xs) { /* code */ } // List a -> List a

debug([4, 3, 2, 1] == toArray(reverse(fromArray([1, 2, 3, 4])))); debug(fromArray([1, 2, 3, 4]) == reverse(reverse(fromArray([1, 2, 3, 4])))); > [LeekySquash] true > [LeekySquash] true

L'opérateur d'égalité == fonctionne implicitement pour nos liste car elles sont constitués de tableaux, mais si nous avions réellement créé un nouveau type de donnée, nous aurions eu à implémenter cet opérateur. C'est donc ce que vous allez faire. Au minimum, vous devriez implémenter equ (==) et lesserThan (), lesserEqu (=).

Bien, tous cela est amusant, mais vous avez probablement envie d'utiliser les listes un peu plus qu'en surface. Par exemple, calculer la taille, récupérer un élément à un indice donné, transformer le contenu, etc. Voici donc une liste (hehe) de fonctions que vous devriez implémenter afin de mieux comprendre cette structure de donnée et comment la manipuler:

Solutions

printInOrder

function printInOrder(xs) { if (empty(xs)) {} else { debug(head(xs)); printInOrder(tail(xs)); } }

printPostOrder

function printPostOrder(xs) { if (empty(xs)) {} else { printPostOrder(tail(xs)); debug(head(xs)); } }

toArray

function toArray(xs) { if (empty(xs)) { return []; } else { return [head(xs)] + toArray(tail(xs)); } }

reverse

function reverse(xs) { var go = function(ys, acc) { return empty(ys) ? acc : go(tail(ys), cons(head(ys), acc)); }; return go(xs, nil()); }

Arbre Binaire

Les listes c'est sympa, (pas trop en LS1), mais cela à un intérêt limité dans le cadre de Leek Wars du aux tableaux. Nous allons maintenant découvrir une structure de donné un peu plus complexe. Si on définit une liste de manière suivante, List a = Nil | Cons a (List a), un arbre binaire sera définit presque de la même manière: Tree a = Nil | Node a (Tree a) (Tree a). Nous pouvons aisément voir qu'une liste est un arbre dont l'une des branches contient toujours Nil. Nous pouvons d'ailleurs aussi considérer que les listes et arbres binaires sont des cas spéciaux de structures de données plus générales, mais nous verrons cela plus tard.

Nous allons d'abord définir les fonctions de manipulation des arbres binaires:

function nil() { return []; } // () -> Tree elem // Instancie un arbre vide. function node(x, ls, rs) { return [x, ls, rs]; } // (elem, Tree elem, Tree elem) -> Tree elem // Assemble deux arbre et un élément en un nouvel arbre. function head(xs) { return xs[0]; } // Tree elem -> elem // Pour récupérer la tête, crash si l'arbre est vide (retourne null en réalité). function left(xs) { return xs[1]; } // Tree elem -> Tree elem // Récupère l'arbre de gauche, même commentaire que pour head function right(xs) { return xs[2]; } // Tree elem -> Tree elem // Récupère l'arbre de droite, même commentaire que pour head function empty(xs) { return xs == nil(); } // Tree elem -> Bool

Forêt

Relation Entre le Récursif et l'Itératif

Continuation Passing Style

Programmation Dynamique

Ou l'élégante force brute.

Si vous n'avez pas encore fait l'exercice avec fibonacci, commencez par là.

Maintenant essayez des valeurs telle que 120. Leekscript ne convertis pas automatiquement les nombres en Bignum donc ne vous inquiétez pas si les résultats sont faux. Par contre, si vous avez correctement implémenté les deux versions, vous avez pu remarquer que la version récursive n'a pas réussi à vous retourner un résultat, tandis que la tail-récursive n'a aucun problème à continuer, et nous n'avons même pas d'élimination de l'appel terminal. Cela vient du fait que pour chaque n > 1, fibonacci est rappelée deux fois, ce qui nous amène à une fonction dont la complexité algorithmique temporelle est O(2^n). (Pas exactement, mais ce qui nous intéresse ici est l'aspect exponentiel.) En comparaison, la version tail-récursive de fibonacci s'exécute en O(n). Nous ne répétons aucun travail au long de la résolution de fibonacci(n). Cependant, la définition récursive de fibonacci est beaucoup plus simple à implémenter et à comprendre que la définition tail-récursive. Nous aimerions donc pouvoir profiter de l'aisance de l'une et les performance de l'autre. Pour cela, il nous faut donc nous assurer de ne pas recalculer inutilement. Nous avons besoin de conserver les résultats intermédiaires. La méthode qui consiste à définir une fonction qui vérifie si un résultat à déjà été calculé et mis en cache puis retourne le résultat, ou le calcule, le stocke, et le retourne, est appelé ''mémoïsation''. Ci-dessous est un exemple basique de fibonacci mémoïsé:

global fibmem = [];

function fibonacci(n) { var ret = fibmem[n]; if (ret !== null) { return ret; } else { if (n memoize une fonction qui prends en paramètre une fonction attendant un argument et retournant cette même fonction mais mémoïsé, nous pouvons définir fibonacci de la sorte:

global fibonacci = memoize(function(n) { return n fibonacci avec une complexité temporelle O(n), mais avec une complexité spatial 0(n) comparé au 0(1) de la définition tail-récursive.

Notions annexe

Des choses intéressantes mais qui ne vous servirons probablement pas.

Voir aussi