Quest-ce que la récursivité de la queue?

La récursion de queue est un cas particulier de récursion où la fonction appelante ne fait plus de calcul après avoir fait un appel récursif. Par exemple, la fonction

 int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } 

est récursive de queue (puisque linstruction finale est un appel récursif) alors que cette fonction nest pas récursive de queue:

 int g(int x) { if (x == 1) { return 1; } int y = g(x-1); return x*y; } 

car il effectue des calculs après le retour de lappel récursif.

La récursivité de queue est importante car elle peut être implémentée plus efficacement que la récursivité générale. Lorsque nous effectuons un appel récursif normal, nous devons pousser ladresse de retour sur la pile dappels puis passer à la fonction appelée. Cela signifie que nous avons besoin dune pile dappels dont la taille est linéaire dans la profondeur des appels récursifs. Lorsque nous avons une récursivité de queue, nous savons que dès que nous revenons de lappel récursif, nous allons également revenir immédiatement, afin de pouvoir ignorer toute la chaîne de fonctions récursives et revenir directement à lappelant dorigine. Cela signifie que nous ne « Pas besoin du tout dune pile dappels pour tous les appels récursifs, et peut implémenter lappel final comme un simple saut, ce qui nous fait gagner de lespace.

Commentaires

• vous avez écrit  » Cela signifie que nous navons ‘ pas besoin dune pile dappels pour tous les appels récursifs « . La pile dappels sera toujours là, juste que ladresse de retour na pas besoin dêtre écrite dans la pile dappels, non?
• Cela dépend de votre modèle de calcul dans une certaine mesure 🙂 Mais oui, sur un vrai ordinateur, le la pile dappels est toujours là, nous ‘ ne lutilisons tout simplement pas.
• Et si elle ‘ est la dernière appel mais pour boucle for. Vous faites donc tous vos calculs ci-dessus mais certains dentre eux dans une boucle for comme def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – ce récursif ne ‘ t se termine.

Simplement dit, la récursivité de queue est une récursion où le compilateur pourrait remplacer lappel récursif avec une commande « goto », donc la version compilée naura pas à augmenter la profondeur de la pile.

Parfois, la conception dune fonction récursive de queue nécessite de créer une fonction dassistance avec des paramètres supplémentaires.

Par exemple, ce nest pas une fonction récursive de queue:

int factorial(int x) { if (x > 0) { return x * factorial(x - 1); } return 1; } 

Mais cest une queue- fonction récursive:

int factorial(int x) { return tailfactorial(x, 1); } int tailfactorial(int x, int multiplier) { if (x > 0) { return tailfactorial(x - 1, x * multiplier); } return multiplier; } 

parce que le compilateur pourrait réécrire la fonction récursive en une fonction non récursive, en utilisant quelque chose comme ceci (un pseudocode):

int tailfactorial(int x, int multiplier) { start: if (x > 0) { multiplier = x * multiplier; x--; goto start; } return multiplier; } 

La règle du compilateur est très simple: lorsque vous trouvez « return thisfunction(newparameters);« , remplacez-le par « 

« . Mais cela ne peut être fait que si la valeur renvoyée par lappel récursif est renvoyée directement.

Si tous les appels récursifs dune fonction peuvent être remplacés comme ceci, alors cest une queue -fonction récursive.

Ma réponse est basée sur lexplication donnée dans le livre Structure et interprétation des programmes informatiques . Je recommande vivement ce livre aux informaticiens.

Approche A: Processus récursif linéaire

(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 

La forme du processus pour Lapproche A ressemble à ceci:

(factorial 5) (* 5 (factorial 4)) (* 5 (* 4 (factorial 3))) (* 5 (* 4 (* 3 (factorial 2)))) (* 5 (* 4 (* 3 (* 2 (factorial 1))))) (* 5 (* 4 (* 3 (* 2 (* 1))))) (* 5 (* 4 (* 3 (* 2)))) (* 5 (* 4 (* 6))) (* 5 (* 24)) 120 

Approche B: processus itératif linéaire

(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) 

La forme du processus pour Approche B ressemble à ceci:

(factorial 5) (fact-iter 1 1 5) (fact-iter 1 2 5) (fact-iter 2 3 5) (fact-iter 6 4 5) (fact-iter 24 5 5) (fact-iter 120 6 5) 120 

Le processus itératif linéaire (approche B) sexécute dans un espace constant même si le processus est une procédure récursive. Il convient également de noter que dans cette approche, un ensemble de variables définit létat du processus à tout moment, à savoir. {product, counter, max-count}. Cest aussi une technique par laquelle la récursion de queue permet loptimisation du compilateur.

Dans lapproche A, il y a plus dinformations cachées que linterpréteur maintient qui sont essentiellement la chaîne dopérations différées.

Commentaires

• Ne devrait ‘ être que (1) au lieu de (* 1)?

Récursivité finale est une forme de récursivité dans laquelle les appels récursifs sont les dernières instructions de la fonction (cest-à-dire doù vient la partie de queue). De plus, lappel récursif ne doit pas être composé avec des références à des cellules mémoire stockant des valeurs précédentes (références autres que les paramètres de la fonction). De cette façon, nous ne nous soucions pas des valeurs précédentes et un cadre de pile suffit pour tous les appels récursifs; tail-recursion est un moyen doptimiser les algorithmes récursifs. Lautre avantage / optimisation est quil existe un moyen simple de transformer un algorithme récursif de queue en un algorithme équivalent qui utilise litération au lieu de la récursivité. Alors oui, lalgorithme de tri rapide est bel et bien récursif en queue.

QUICKSORT(A, p, r) if(p < r) then q = PARTITION(A, p, r) QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r) 

Voici la version itérative:

QUICKSORT(A) p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) r = q - 1 p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) p = q + 1