Chapitre 06 - Recursive programming Flashcards
Pourquoi a t’on besoin de la récursion
En programmation fonctionnelle, les fonctions étant pure, il ne sert à rien de faire des boucles. Ce qui est interessant ce sont les appels imbriqués f(f(f(x))) d’ou la récursivité
Peut-on remplacer toutes les boucles avec mutables ?
Oui c’est toujours possible avec de la récursion et des valeurs immutables
Exemple d’algorithme récursif
Hanoi et Factorielle
Quelle est le principe de base derrière les algorithmes récursifs
Que le gros problème se décompose en sous problème qui peuvent si nécessaire se redécomposer.
Quelles sont les 3 éléments majeurs dont il faut tenir compte lors de la réalisation d’un algorithme récursif
1/ Au moins une branche ne doit pas être récursive
2/ Tous les sous problèmes doivent résoudre une sous partie du problème initial (et pas augmenter)
3/ le focus doit se faire sur la réalisation du plus petit problème de base pas sur le récursif
Exemples de structures récursives
Arbre et Lists
Qu’est-ce que le tail recursion optimisation
Le problème de la récursion c’est la pile d’appel. Le tail recursion optimisation a pour but de transformer la récursion en une boucle.
Quand est possible le tail recursion optimisation
Quand la dernière ligne de la fonction est un appel vers le résultat d’une fonction
Quand est possible le tail recursion optimisation
Quand la dernière ligne de la fonction est un appel vers le résultat d’une fonction