Bonjour, Habr!
Aujourd'hui, nous poursuivons nos recherches sur la programmation fonctionnelle dans le contexte d'EcmaScript, dont la spécification est basée sur JavaScript. Dans les articles précédents du cycle, les sujets suivants ont été examinés:
- Fonctions pures, lambdas, immunité
- Composition, curry, application partielle
Récursivité
Comme toujours, Wikipedia nous aide à trouver une définition:
Récursivité - la définition, la description, l'image d'un objet ou d'un processus à l'intérieur de cet objet ou processus lui-même, c'est-à-dire la situation où l'objet fait partie de lui-même. Le terme «récursivité» est utilisé dans divers domaines particuliers de la connaissance - de la linguistique à la logique, mais trouve la plus grande application en mathématiques et en informatique.
Pour la programmation, la récursivité se réfère aux
processus qui s'invoquent dans leur corps . Une fonction récursive a plusieurs composants obligatoires:
- Condition terminale - condition de terminaison
- La règle qui pénètre profondément dans la récursivité
Prenons l'exemple le plus populaire de calcul récursif-factoriel.
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); }
Nous distinguons les composants caractéristiques d'une fonction récursive. État des bornes
if (n === 0) { return 1; }
et règle de récursivité
return n * factorial(n - 1);
Il est important de réaliser que la récursivité n'est pas une caractéristique spécifique de JS, mais une technique très courante en programmation.
Processus récursifs et itératifs
La récursivité peut être organisée de deux manières: par un processus récursif ou par un processus itératif.
Nous avons déjà vu le processus récursif:
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); }
Une solution itérative au problème factoriel ressemblerait à ceci:
const factorial = (n) => { const iter = (counter, acc) => { if (counter === 1) { return acc; } return iter(counter - 1, counter * acc); }; return iter(n, 1); };
Ces deux options sont récursives. Les deux solutions ont des caractéristiques caractéristiques de la récursivité: la condition terminale et la règle de mouvement le long de la récursivité. Regardons leurs différences.
Le processus récursif à chaque étape se souvient de l'action. qui doit être fait. Ayant atteint les conditions thermiques, il effectue toutes les actions mémorisées dans l'ordre inverse. Illustrons par un exemple. Lorsque le processus récursif considère le factoriel 6, il doit se souvenir de 5 nombres afin de les compter à la toute fin, lorsque vous ne pouvez aller nulle part et que vous ne pouvez plus aller plus loin dans les profondeurs. Lorsque nous sommes dans le prochain appel de fonction, quelque part en dehors de cet appel, ces numéros mémorisés sont stockés en mémoire.
Cela ressemble à ceci:
factorial(3);
Comme vous pouvez le voir, l'idée de base d'un processus récursif est de reporter le calcul à la fin.
Un tel processus génère
un état variant dans le temps qui est stocké «quelque part» en dehors de l'appel de fonction en cours.
Je pense que vous vous souvenez que dans le premier article de la série sur la
programmation fonctionnelle, nous avons parlé de l'importance de l'immunité et du manque d'état. Avoir une condition pose de nombreux problèmes qui ne sont pas toujours faciles à gérer.
Un processus itératif diffère d'un
processus récursif dans un nombre fixe d'états. À chaque étape, le processus itératif considère tout ce qu'il peut calculer, de sorte que chaque étape de la récursivité existe indépendamment de la précédente.
Cela ressemble à ceci:
iter(3, 1);
Je pense qu'il est évident qu'un processus itératif consomme moins de mémoire. Par conséquent, vous devez toujours l'utiliser lors de la création d'une récursivité. La seule exception: si nous ne pouvons pas calculer la valeur jusqu'à ce que la condition thermique soit atteinte.
Récursivité des arbres
Beaucoup de gens pensent que les arbres et travailler avec eux sont quelque chose de très abstrus, complexe et incompréhensible pour les simples mortels. Ce n'est en fait pas le cas. Toute structure hiérarchique peut être représentée sous la forme d'un arbre. Même la pensée humaine est comme un arbre.
Pour mieux comprendre la récursivité des arbres, examinons un exemple simple et populaire - les nombres de Fibonacci.
Nombres de Fibonacci - éléments d'une séquence numérique 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, ... (séquence A000045 dans OEIS), dans laquelle les deux premiers nombres sont soit 1 et 1, soit 0 et 1, et chaque nombre suivant est égal à la somme des deux nombres précédents. Nommé d'après le mathématicien médiéval Leonardo de Pise (connu sous le nom de Fibonacci).
Mathématiquement, il est assez simple de formuler une description (et la programmation déclarative est la description) de cette séquence:
fib(n) = [ 0 n = 0,//(1) 1 n = 1,//(2) fib(n-1) + fib(n-2) ]
Passons maintenant des mathématiques au raisonnement logique (après tout, nous devons écrire la logique du programme). Pour calculer fib (5), nous devons calculer fib (4) et fib (3). Pour calculer fib (4), nous devons calculer fib (3) et fib (2). Pour calculer fib (3), nous devons calculer fib (2) et ainsi de suite jusqu'à ce que nous arrivions aux valeurs connues (1) et (2) dans notre modèle mathématique.
À quelles pensées notre raisonnement devrait-il nous conduire? Évidemment, nous devons utiliser la récursivité. La condition thermique peut être formulée comme n <= 1. Cependant, au lieu d'une branche de récursivité (comme dans les exemples précédents), nous aurons deux branches: fib (n-1), fib (n-2).
const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2));
Cette solution a un inconvénient important! Il considère le résultat de la même valeur de n plusieurs fois dans différentes branches. Pour résoudre ce problème, il existe une technique de programmation fonctionnelle appelée
mémorisation , dont nous parlerons dans l'un des articles suivants.
Conclusion
La récursivité est un outil de programmation très puissant. Permettez-moi de vous rappeler qu'en règle générale, nous utilisons un processus itératif. Cela vaut la peine d’utiliser un processus récursif uniquement si nous ne pouvons pas calculer le résultat intermédiaire à chaque étape de la récursivité.