Y at-il des problèmes qui ne peuvent pas être écrits en utilisant la récursion de la queue?

Question

La récursion de la queue est une stratégie importante d'optimisation des performances dans les langages fonctionnels, car elle permet aux appels récursifs de consommer une pile constante (plutôt que O (n)).

Existe-t-il des problèmes qui ne peuvent tout simplement pas être écrits dans un style récursif, ou est-il toujours possible de convertir une fonction naïvement récursive en une fonction récursive?

Si tel est le cas, les compilateurs et interprètes fonctionnels seront-ils un jour suffisamment intelligents pour effectuer la conversion automatiquement?

Answer 1

Oui, en fait, vous pouvez prendre un peu de code et de convertir chaque appel de fonction, et que chaque retour dans une queue d'appel. Ce que vous finissez avec est appelé continuation passing style, ou CPS.

Par exemple, voici une fonction contenant deux appels récursifs:

(define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))
    1))

Et voici à quoi il devrait ressembler si vous avez converti cette fonction pour la continuation, passant du style:

(define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

L'argument supplémentaire, ctn, est une procédure qui count-tree-cps de la queue-les appels au lieu de revenir. (sdcvvc la réponse dit que vous ne pouvez pas tout faire en O(1) de l'espace, et que c'est correct; ici, chaque suite est une fermeture qui prend de la mémoire.)

Je n'ai pas transformer les appels à l' car ou cdr ou + en queue-les appels. Qui pourrait être aussi bien fait, mais je suppose que ceux de la feuille d'appels serait effectivement insérée.

Maintenant pour la partie la plus amusante. Poulet Régime ne fait cette conversion sur la totalité du code, il compile. Les procédures compilées par le Poulet ne jamais revenir. Il y a un article classique expliquant pourquoi le Poulet Régime de cela, écrit en 1994, avant de Poulet a été mis en œuvre: les INCONVÉNIENTS ne doivent pas contre ses arguments, Partie II: Cheney sur le M. T. A.

De manière assez surprenante, la continuation passing style est assez commun en JavaScript. Vous pouvez l'utiliser pour faire de longue calcul, en évitant le navigateur de script lent" popup. Et il est attractif pour des Api asynchrones. jQuery.get (un simple wrapper autour de XMLHttpRequest) est clairement dans le prolongement de passage de style; le dernier argument est une fonction.

Answer 2

C'est vrai, mais pas utile de faire observer que n'importe quelle collection de fonctions mutuellement récursives peut être transformé en une queue-fonction récursive. Cette observation est sur un pied d'égalité avec les vieux châtaigniers bof les années 1960 que le contrôle des flux de constructions pourraient être éliminé parce que chaque programme peut être écrit comme une boucle avec une instruction de cas imbriquées à l'intérieur.

Ce qui est utile à savoir, c'est que beaucoup de fonctions qui ne sont pas évidemment la queue-récursive peut être converti à la queue-récursive forme par l'ajout d' accumuler des paramètres. (Une version extrême de cette transformation est la transformation de la continuation passing style (CPS), mais la plupart des programmeurs trouver la sortie de la CPS transformer difficile à lire.)

Voici un exemple d'une fonction qui est "récursive" (en fait c'est juste de l'itération), mais pas la queue-récursive:

factorial n = if n == 0 then 1 else n * factorial (n-1)

Dans ce cas multiplier, se passe après l'appel récursif. Nous pouvons créer une version de la queue récursive en mettant le produit en une accumulation de paramètre:

factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

La fonction interne f est récursives terminales et les compile dans une boucle.

---

- Je trouver les distinctions suivantes utile:

• Dans un processus itératif ou récursif programme, pour résoudre un problème de taille npar première résolution de l'un subproblem de la taille de l' n-1. Le calcul de la fonction factorielle tombe dans cette catégorie, et cela peut être fait de manière itérative ou de manière récursive. (Cette idée se généralise, par exemple, à la fonction de Fibonacci, où vous avez besoin d' n-1 et n-2 pour résoudre n.)

• Dans un programme récursif, pour résoudre un problème de taille n par la première résolution de deux sous-problèmes de taille n/2. Ou, plus généralement, pour résoudre un problème de taille n par le premier de la résolution d'un subproblem de la taille de l' k et un de taille n-koù 1 < k < n. Quicksort et mergesort sont deux exemples de ce type de problème, qui peut facilement être programmé de manière récursive, mais n'est pas si facile à programmer de manière itérative, ou en utilisant uniquement la queue de la récursivité. (Essentiellement pour simuler la récursivité à l'aide d'un explicite la pile.)

• La programmation dynamique, vous résoudre un problème de taille n par la première résolution de tous les sous-problèmes de toutes tailles, koù k<n. Trouver le chemin le plus court d'un point à un autre dans le Métro de Londres est un exemple de ce type de problème. (Le Métro de Londres est une multipliez-graphe connexe, et vous résoudre le problème en commençant par la recherche de tous les points pour lesquels le chemin le plus court se trouve à 1 arrêt, alors, pour qui le chemin le plus court est à 2 arrêts, etc, etc.)

Seul le premier type de programme a une simple transformation en queue-forme récursive.

Answer 3

Tout algorithme récursif peut être réécrit comme un algorithme itératif (peut-être besoin d'une pile ou d'une liste) et les algorithmes itératifs peuvent toujours être réécrit comme la queue d'algorithmes récursifs, donc je pense que c'est vrai que toute solution récursive peut en quelque sorte être convertie en une queue-solution récursive.

(Dans les commentaires, Pascal Cuoq souligne que tout algorithme peut être converti à la continuation passing style.)

Notez que juste parce que quelque chose est récursives terminales ne veut pas dire que son utilisation de la mémoire est constante. Cela signifie simplement que l'appel-le retour de la pile de ne pas grandir.

Answer 4

Vous ne pouvez pas tout faire en O(1) de l'espace (espace théorème de hiérarchie). Si vous insistez sur l'utilisation de la récursivité tail, alors vous pouvez stocker la pile d'appel comme l'un des arguments. Évidemment, cela ne change rien; quelque part en interne, il y a une pile d'appels, vous êtes simplement en faisant explicitement visible.

Si oui, un jour peut-fonctionnelle compilateurs et interprètes être assez intelligent pour effectuer la conversion automatiquement?

Une telle conversion ne fera pas diminuer l'espace de la complexité.

Comme Pascal Cuoq a commenté, une autre façon est d'utiliser des CPS; tous les appels sont queue récursive ensuite.

Answer 5

Je ne pense pas que quelque chose comme tak pourrait être mis en œuvre en utilisant uniquement les appels de queue. (n'autorisant pas les poursuites)