Récursion de la queue en C ++

Quelqu’un peut-il me montrer une simple fonction récursive en C ++?

Pourquoi la récursion de la queue est-elle meilleure, si c’est le cas?

Quels sont les autres types de récursivité en dehors de la récursion de la queue?

Une simple fonction récursive de la queue:

 unsigned int f( unsigned int a ) { if ( a == 0 ) { return a; } return f( a - 1 ); // tail recursion } 

La récursion de la queue est essentiellement quand:

  • il n’y a qu’un seul appel récursif
  • cet appel est la dernière déclaration de la fonction

Et ce n’est pas “mieux”, sauf en ce sens qu’un bon compilateur peut supprimer la récursivité, la transformant en boucle. Cela peut être plus rapide et permettra certainement d’économiser sur l’utilisation de la stack. Le compilateur GCC peut effectuer cette optimisation.

La récurrence de la queue en C ++ ressemble à C ou à toute autre langue.

 void countdown( int count ) { if ( count ) return countdown( count - 1 ); } 

La récursion de la queue (et l’appel de queue en général) nécessite d’effacer le cadre de la stack de l’appelant avant d’exécuter l’appel de queue. Pour le programmeur, la récursion de la queue est similaire à une boucle, avec un return réduit à travailler comme goto first_line; . Le compilateur doit cependant détecter ce que vous faites et si ce n’est pas le cas, il y aura toujours un cadre de stack supplémentaire. La plupart des compilateurs le supportent, mais écrire une boucle ou un goto est généralement plus facile et moins risqué.

Les appels de queue non récursifs peuvent permettre un twigment aléatoire (comme un goto à la première ligne d’une autre fonction), ce qui est une fonctionnalité plus unique.

Notez qu’en C ++, il ne peut y avoir aucun object avec un destructeur non sortingvial dans la scope de l’instruction return . Le nettoyage de fin de fonction nécessiterait que l’appelé retourne à l’appelant, éliminant l’appel de queue.

Notez également (dans n’importe quel langage) que la récursion de la queue nécessite que l’état complet de l’algorithme soit transmis à la liste des arguments de la fonction à chaque étape. (Cela ressort clairement de l’exigence selon laquelle le cadre de la fonction doit être éliminé avant le prochain appel… vous ne pouvez enregistrer aucune donnée dans les variables locales.) De plus, aucune opération ne peut être appliquée à la fonction .

 int factorial( int n, int acc = 1 ) { if ( n == 0 ) return acc; else return factorial( n-1, acc * n ); } 

La récursion de la queue est un cas particulier d’un appel de queue. Un appel de queue est l’endroit où le compilateur peut voir qu’il n’y a pas d’opération à effectuer après le retour d’une fonction appelée – transformant essentiellement le retour de la fonction appelée en son propre. Le compilateur peut souvent effectuer quelques opérations de correction de la stack, puis sauter (plutôt que d’appeler) l’adresse de la première instruction de la fonction appelée .

Outre l’élimination des appels de retour, l’un des avantages est que vous réduisez également l’utilisation de la stack. Sur certaines plates-formes ou dans le code du système d’exploitation, la stack peut être assez limitée et, sur des machines avancées comme les processeurs x86 de nos ordinateurs de bureau, réduire la consommation de stack améliore les performances du cache de données.

La récursion de la queue est l’endroit où la fonction appelée est la même que la fonction appelante. Cela peut être transformé en boucles, ce qui est exactement le même que le saut dans l’optimisation des appels de queue mentionnée ci-dessus. Comme il s’agit de la même fonction (appelé et appelé), il y a moins de corrections de stack à effectuer avant le saut.

Ce qui suit montre un moyen courant de faire un appel récursif qui serait plus difficile pour un compilateur de se transformer en boucle:

 int sum(int a[], unsigned len) { if (len==0) { return 0; } return a[0] + sum(a+1,len-1); } 

C’est assez simple pour que de nombreux compilateurs puissent le trouver de toute façon, mais comme vous pouvez le constater, un ajout doit être effectué après que le retour de la sum appelée retourne un nombre.

Si vous avez fait:

 static int sum_helper(int acc, unsigned len, int a[]) { if (len == 0) { return acc; } return sum_helper(acc+a[0], len-1, a+1); } int sum(int a[], unsigned len) { return sum_helper(0, len, a); } 

Vous seriez en mesure de tirer parti des appels dans les deux fonctions étant des appels de queue. La tâche principale de la fonction sum consiste à déplacer une valeur et à effacer une position de registre ou de stack. Le sum_helper fait tout le calcul.

Puisque vous avez mentionné C ++ dans votre question, je mentionnerai des choses spéciales à ce sujet. C ++ cache certaines choses de vous que C ne contient pas. Parmi ces destructeurs, la principale est l’optimisation des appels de queue.

 int boo(yin * x, yang *y) { dharma z = x->foo() + y->bar(); return z.baz(); } 

Dans cet exemple, l’appel à baz n’est pas vraiment un appel de queue, car z doit être détruit après le retour de baz. Je crois que les règles de C ++ peuvent rendre l’optimisation plus difficile, même dans les cas où la variable n’est pas nécessaire pour la durée de l’appel, comme par exemple:

 int boo(yin * x, yang *y) { dharma z = x->foo() + y->bar(); int u = z.baz(); return qwerty(u); } 

z peut être détruit après le retour de qwerty ici.

Une autre chose serait la conversion de type implicite, qui peut également se produire en C, mais peut être plus compliquée et plus courante en C ++. Par exemple:

 static double sum_helper(double acc, unsigned len, double a[]) { if (len == 0) { return acc; } return sum_helper(acc+a[0], len-1, a+1); } int sum(double a[], unsigned len) { return sum_helper(0.0, len, a); } 

Ici, l’appel de sum à sum_helper n’est pas un appel de fin, car sum_helper renvoie un double et la sum devra la convertir en un int.

En C ++, il est courant de renvoyer une référence d’object qui peut avoir toutes sortes d’interprétations différentes, chacune pouvant être une conversion de type différente. Par exemple:

 bool write_it(int it) { return cout << it; } 

Ici, il y a un appel à cout.operator << comme dernière déclaration. cout renverra une référence à lui-même (c'est pourquoi vous pouvez enchaîner beaucoup de choses dans une liste séparée par <<), que vous forcerez ensuite à évaluer en tant que booléen, ce qui finira par appeler une autre méthode de cout, l'opérateur bool ( ). Ce cout.operator bool () pourrait être appelé comme un appel de queue dans ce cas, mais operator << ne pourrait pas.

MODIFIER:

Une chose qui mérite d'être mentionnée est que l'une des principales raisons pour lesquelles l'optimisation des appels de queue en C est possible est que le compilateur sait que la fonction appelée stockera sa valeur de retour au même endroit que la fonction appelante stocké dans.

La récursion de la queue n’existe pas vraiment au niveau du compilateur en C ++.

Bien que vous puissiez écrire des programmes qui utilisent la récursivité de queue, vous n’obtenez pas les avantages inhérents à la récursion de queue implémentée en prenant en charge les compilateurs / interprètes / langages. Par exemple, Scheme prend en charge une optimisation de la récursion de la queue afin que celle-ci change fondamentalement la récursivité. Cela le rend plus rapide et invulnérable pour emstackr les débordements. C ++ n’a pas une telle chose. (moins aucun compilateur que j’ai vu)

Des optimisations de la récursion de la queue existent apparemment à la fois dans MSVC ++ et GCC. Voir cette question pour plus de détails.

Wikipedia a un article décent sur la récursion de la queue . Fondamentalement, la récursion de la queue est meilleure que la récursivité régulière car il est sortingvial de l’optimiser dans une boucle itérative, et les boucles itératives sont généralement plus efficaces que les appels de fonction récursifs. Ceci est particulièrement important dans les langages fonctionnels où vous n’avez pas de boucles.

Pour C ++, c’est toujours bien si vous pouvez écrire vos boucles récursives avec une récursion de queue car elles peuvent être mieux optimisées, mais dans ce cas, vous pouvez généralement le faire itérativement, donc le gain n’est pas aussi élevé qu’il le ferait. être dans un langage fonctionnel.

La récursion de la queue est une astuce pour faire face à deux problèmes en même temps. Le premier consiste à exécuter une boucle lorsqu’il est difficile de connaître le nombre d’itérations à effectuer.

Bien que cela puisse être résolu avec une récursivité simple, le deuxième problème se pose, à savoir celui du dépassement de capacité dû à l’appel récursif exécuté trop de fois. L’appel de queue est la solution lorsqu’il est accompagné d’une technique de calcul et de transfert.

Dans le CS de base, vous apprenez qu’un algorithme informatique doit avoir un invariant et une condition de terminaison. Ceci est la base pour la construction de la récursion de la queue.

  1. Tout calcul se passe dans l’argument passant.
  2. Tous les résultats doivent être transmis aux appels de fonction.
  3. L’appel de fin est le dernier appel et se produit à la fin.

Pour le dire simplement, aucun calcul ne doit avoir lieu sur la valeur de retour de votre fonction .

Prenons par exemple le calcul d’une puissance de 10, ce qui est sortingvial et peut être écrit par une boucle.

Devrait ressembler à quelque chose

 template T pow10(T const p, T const res =1) { return p ? res: pow10(--p,10*res); } 

Cela donne une exécution, par exemple 4:

ret, p, res

-, 4,1

-, 3,10

-, 2 100

– 1,1000

-, 0,10000

10000, -, –

Il est clair que le compilateur doit simplement copier les valeurs sans changer le pointeur de la stack et quand l’appel de queue se produit simplement pour renvoyer le résultat.

La récursion de la queue est très importante car elle peut fournir des évaluations de temps de compilation prêtes à l’emploi, par exemple, ce qui peut être fait.

 template struct powc10 { int operator()() const { return powc10()(); } }; template struct powc10<0,R> { int operator()() const { return R; } }; 

Cela peut être utilisé comme powc10<10>()() pour calculer la 10ème puissance au moment de la compilation.

La plupart des compilateurs ont une limite d’appels nesteds, de sorte que l’astuce d’appel de queue aide. Evidemment, il n’y a pas de boucles de programmation de méta, donc vous devez utiliser la récursivité.