Les langages fonctionnels sont-ils meilleurs en récurrence?

TL; DR: Les langages fonctionnels gèrent-ils mieux la récursion que les non-fonctionnels?

Je lis actuellement Code Complete 2. À un moment donné du livre, l'auteur nous met en garde contre la récursion. Il dit que cela devrait être évité autant que possible et que les fonctions utilisant la récursion sont généralement moins efficaces qu'une solution utilisant des boucles. À titre d’exemple, l’auteur a écrit une fonction Java qui utilise la récursivité pour calculer la factorielle d’un nombre comme celui-ci (ce n’est peut-être pas exactement la même chose puisque je n’ai pas le livre avec moi pour le moment):

public int factorial(int x) {
    if (x <= 0)
        return 1;
    else
        return x * factorial(x - 1);
}

Ceci est présenté comme une mauvaise solution. Cependant, dans les langages fonctionnels, la récursivité est souvent la méthode préférée. Par exemple, voici la fonction factorielle dans Haskell utilisant la récursivité:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

Et est largement accepté comme une bonne solution. Comme je l'ai vu, Haskell utilise très souvent la récursivité et je n'ai vu nulle part où elle était mal vue.

Donc, ma question est essentiellement la suivante:

• Les langages fonctionnels gèrent-ils mieux la récursion que les non fonctionnels?

EDIT: Je suis conscient que les exemples que j'ai utilisés ne sont pas les meilleurs pour illustrer ma question. Je voulais juste souligner que Haskell (et les langages fonctionnels en général) utilise la récursion beaucoup plus souvent que les langages non fonctionnels.

Oui, ils le font, mais pas seulement parce qu'ils le peuvent , mais parce qu'ils doivent le faire .

Le concept clé ici est la pureté : une fonction pure est une fonction sans effets secondaires et sans état. Les langages de programmation fonctionnels embrassent généralement la pureté pour de nombreuses raisons, telles que le raisonnement sur le code et l’évitement des dépendances non évidentes. Certaines langues, notamment Haskell, vont même jusqu'à ne permettre que du code pur; tous les effets secondaires qu'un programme peut avoir (tels que l'exécution d'E / S) sont déplacés vers un environnement d'exécution non pur, ce qui garde le langage pur.

Ne pas avoir d’effets secondaires signifie que vous ne pouvez pas avoir de compteurs de boucle (car un compteur de boucle constituerait un état mutable, et la modification de cet état constituerait un effet secondaire). Par conséquent, le langage le plus itératif qu’un langage purement fonctionnel puisse obtenir consiste à itérer sur une liste ( cette opération est généralement appelée foreachou map). La récursion, cependant, est une correspondance naturelle avec la programmation fonctionnelle pure: aucun état n'est nécessaire pour la récurrence, à l'exception des arguments de la fonction (lecture seule) et d'une valeur de retour (écriture seule).

Cependant, ne pas avoir d'effets secondaires signifie également que la récursivité peut être implémentée plus efficacement et que le compilateur peut l'optimiser de manière plus agressive. Je n'ai pas étudié ce compilateur en profondeur moi-même, mais pour autant que je sache, la plupart des compilateurs de langages de programmation fonctionnels optimisent l'optimisation d'appels, et certains peuvent même compiler certains types de constructions récursives en boucles en arrière-plan.

Vous comparez la récursivité par rapport à l'itération. Sans élimination de l'appel final , l'itération est en effet plus efficace car il n'y a pas d'appel de fonction supplémentaire. De plus, l'itération peut durer indéfiniment, alors qu'il est possible de manquer d'espace dans la pile suite à un trop grand nombre d'appels de fonction.

Cependant, l'itération nécessite de changer de compteur. Cela signifie qu'il doit y avoir une variable mutable , qui est interdite dans un cadre purement fonctionnel. Les langages fonctionnels sont donc spécialement conçus pour fonctionner sans itération, d'où les appels de fonctions simplifiés.

Mais rien de tout cela ne permet de comprendre pourquoi votre exemple de code est si élégant. Votre exemple illustre une propriété différente, qui correspond à un motif . C'est pourquoi l'échantillon Haskell ne contient pas de conditions explicites. En d'autres termes, ce n'est pas la récursion rationalisée qui rend votre code petit; c'est le motif correspondant.

Techniquement non, mais pratiquement oui.

La récursivité est beaucoup plus courante lorsque vous adoptez une approche fonctionnelle du problème. En tant que tels, les langages conçus pour utiliser une approche fonctionnelle incluent souvent des fonctionnalités qui rendent la récursion plus facile / meilleure / moins problématique. De prime abord, il y a trois points communs:

1. Optimisation de l'appel de queue. Comme indiqué par d'autres affiches, les langages fonctionnels nécessitent souvent un TCO.

2. Évaluation paresseuse. Haskell (et quelques autres langues) est évalué paresseusement. Cela retarde le «travail» réel d'une méthode jusqu'à ce qu'il soit requis. Cela tend à conduire à des structures de données plus récursives et, par extension, à des méthodes récursives pour les utiliser.

3. Immutabilité. La majorité des éléments avec lesquels vous travaillez dans des langages de programmation fonctionnels sont immuables. Cela facilite la récursivité car vous n'avez pas à vous préoccuper de l'état des objets dans le temps. Vous ne pouvez pas avoir une valeur modifiée en dessous de vous, par exemple. En outre, de nombreuses langues sont conçues pour détecter des fonctions pures . Puisque les fonctions pures n’ont pas d’effets secondaires, le compilateur a beaucoup plus de liberté quant à l’ordre dans lequel les fonctions s’exécutent et aux autres optimisations.

Aucune de ces choses n'est vraiment spécifique aux langages fonctionnels par rapport aux autres, donc elles ne sont pas simplement meilleures parce qu'elles sont fonctionnelles. Mais comme elles sont fonctionnelles, les décisions de conception prises tendent vers ces fonctionnalités car elles sont plus utiles (et leurs inconvénients moins problématiques) lors de la programmation fonctionnelle.

Haskell et d'autres langages fonctionnels utilisent généralement l'évaluation paresseuse. Cette fonctionnalité vous permet d'écrire des fonctions récursives sans fin.

Si vous écrivez une fonction récursive sans définir de cas de base où la récursion se termine, vous obtenez des appels infinis à cette fonction et à un flux de pile supérieur.

Haskell prend également en charge les optimisations d'appels de fonction récursives. En Java, chaque appel de fonction s'empile et entraîne une surcharge.

Alors oui, les langages fonctionnels gèrent mieux la récursivité que d’autres.

La seule raison technique que je connaisse est que certains langages fonctionnels (et certains langages impératifs, si je me souviens bien) ont ce qu'on appelle l'optimisation d'appel final qui permet à une méthode récursive de ne pas augmenter la taille de la pile à chaque appel récursif (c'est-à-dire l'appel récursif plus ou moins remplace l'appel en cours sur la pile).

Notez que cette optimisation ne fonctionne sur aucun appel récursif, mais uniquement sur les méthodes récursives d’appel final (c.-à-d. Les méthodes qui ne conservent pas l’état au moment de l’appel récursif).

Vous voudrez peut-être examiner Garbage Collection is Fast, mais une pile est plus rapide , un article sur l'utilisation de ce que les programmeurs C penseraient de "tas" pour les cadres de pile compilés en C. Je crois que l'auteur a bricolé avec Gcc pour le faire. . Ce n'est pas une réponse définitive, mais cela pourrait vous aider à comprendre certains problèmes liés à la récursivité.

Le langage de programmation Alef , qui accompagnait Plan 9 de Bell Labs, comportait un énoncé "devenu" (voir la section 6.6.4 de cette référence ). C'est une sorte d'optimisation explicite de récursivité d'appel final. Le "mais il utilise la pile d'appels!" l'argument contre la récursion pourrait éventuellement être éliminé.

TL; DR: Oui, la
récursivité est un outil essentiel de la programmation fonctionnelle. C'est pourquoi nous avons beaucoup travaillé sur l'optimisation de ces appels. Par exemple, R5RS exige (dans la spécification!) Que toutes les implémentations gèrent les appels de récursion non liés sans que le programmeur se préoccupe du débordement de la pile. À des fins de comparaison, par défaut, le compilateur C n’effectuera même pas une optimisation évidente de l’appel final (essayez un verso récursif d’une liste chaînée) et après quelques appels, le programme s’arrêtera (le compilateur optimisera cependant, si vous utilisez - O2).

Bien sûr, dans les programmes qui sont horriblement écrits, comme le célèbre fibexemple qui est exponentiel, le compilateur n'a que peu ou pas d'options pour faire sa "magie". Il faut donc veiller à ne pas entraver les efforts d'optimisation du compilateur.

EDIT: Par le fib exemple, je veux dire ce qui suit:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)

Les langages fonctionnels conviennent mieux à deux types de récursivité très spécifiques: la récursion de queue et la récursion infinie. Elles sont aussi mauvaises que d’autres langues dans d’autres types de récursivité, comme dans votre factorialexemple.

Cela ne veut pas dire qu’aucun algorithme ne fonctionne bien avec une récursion régulière dans les deux paradigmes. Par exemple, tout ce qui nécessite de toute façon une structure de données de type pile, telle qu'une recherche arborescente en profondeur d'abord, est le plus simple à implémenter avec la récursion.

La récursion revient plus souvent avec la programmation fonctionnelle, mais elle est également beaucoup utilisée, en particulier par les débutants ou dans les tutoriels pour débutants, peut-être parce que la plupart des débutants en programmation fonctionnelle ont déjà utilisé la récursivité dans la programmation impérative. Il existe d'autres structures de programmation fonctionnelles, telles que la compréhension de listes, les fonctions d'ordre supérieur et d'autres opérations sur les collections, qui sont généralement beaucoup mieux adaptées conceptuellement, au style, à la concision, à l'efficacité et à l'optimisation.

Par exemple, la suggestion de delnan factorial n = product [1..n]est non seulement plus concise et plus facile à lire, mais aussi hautement parallélisable. Même chose pour utiliser foldou reducesi votre langue n'a pas productdéjà été intégrée. La récursion est la solution de dernier recours pour résoudre ce problème. La principale raison pour laquelle vous le voyez résoudre de manière récursive dans les tutoriels est un point de départ avant de trouver de meilleures solutions, et non un exemple de meilleure pratique.