Chapitre 07 - Recursion on lists Flashcards
Qu’est-ce qu’il y a derrière toute les fonctions recursives
il y a une égalité récursive
comment envisager la récursivité
la solution d’un problème est égal à la solution d’un problème plus petit en recursion
Comment cela aide t’il à la conception de la récursion de connaitre l’équation d’égalité récursive
On se focalise sur le résultat voulue plut^tot que sur l’implémentation elle-même
Exemple d’égalité récursive
dernier de la liste Last(list) = Last(tail(list))
factorielle fact(n) = n * fact(n-1)
est-ce que l’égalité récursive est suffisante?
Non elle agit souvent sur un sous ensemble de données, il faut prendre en compte des valeurs extremes comme des listes vides
Exemple d’une structure de données fonctionnelle très adapté à la récursivité
Les listes sont construites selon une méthode récursive (head, tail => liste) donc très adapté à de la récursivité
Comment transformer une opération non-tail recursive en tail recursive
La solution est souvent de déclarer une fonction “interne” avec un accumulateur en nouveau paramètre
Exemple de transformation d’une fonction de list en tail recursive
length(list)
function addLength(list, length)
case nil => len
case _ :: tail => addLength(tail, length + 1)
addLength(list,0)
opposé à length
case nil => 0
case _ :: tail => 1 + length(tail)
Dans la transformation en tail recursive d’un accumulateur en forme de liste à quoi faut-il faire attention
Dans le cas d’un accumulateur de liste, il est préférable de construire la liste en ajoutant depuis le “front” pour éviter d’aller à la fin de la liste à chaque fois qui est une opération couteuse
Quelle est la bonne alternative, construire une liste en ordre inversé avec la méthode “front” ou faire une liste en ajoutant à la fin
Il est moins couteux de renverser une liste après avoir fait du front que d’avoir une liste parfaite avec la très couteuse insertion à la fin
Quelle technique permet de gérer des listes de grande taille impacté par l’immutabilité
On met dans les fonctions qui les traite des variables mutables pour éviter des couts de copie. Si la variable mutable est locale, la fonction reste pure
