Récursion de la queue en C++

Question

Quelqu'un peut-il me montrer une fonction simple de récurrence de la queue en C++ ?

Pourquoi la récursion de queue est-elle meilleure, si tant est qu'elle le soit ?

Quels autres types de récursion existe-t-il en dehors de la récursion de queue ?

Answer 1

Une fonction récursive à queue simple :

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 dans le sens où un bon compilateur peut supprimer la récursion, la transformant en une boucle. Cela peut être plus rapide et permettra certainement d'économiser l'utilisation de la pile. Le compilateur GCC peut faire cette optimisation.

Answer 2

La récusion de la queue en C++ ressemble à celle du C ou de tout autre langage.

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

La récursion de queue (et l'appel de queue en général) efface par définition le cadre de la pile de la fonction avant d'exécuter l'appel suivant. La récursion de queue est la même chose qu'une boucle, presque une simple différence stylistique. La plupart des compilateurs la supportent, mais les boucles sont à la fois plus faciles et moins risquées.

Les appels de queue peuvent permettre des branchements aléatoires (comme un goto vers la première ligne d'une fonction), ce qui est une fonction plus unique.

Notez qu'en C++, si vous avez des objets à détruire, le nettoyage de fin de fonction peut l'empêcher.

EDITAR: Puisqu'il semble y avoir une certaine confusion ici, notez que la récursion de queue exige que l'état de l'algorithme soit entièrement passé dans les arguments de la fonction à chaque étape. (Cela ressort clairement de l'exigence selon laquelle le cadre de la pile de la fonction doit être éliminé avant que l'appel suivant ne commence vous ne pouvez pas sauvegarder de données dans des variables locales). De plus, aucune opération ne peut être appliquée à la valeur de retour de la fonction avant qu'elle ne soit retournée par la queue.

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

Answer 3

La récursion de queue est un cas particulier de l'appel de queue. Un appel de queue est un cas où le compilateur peut voir qu'il n'y a pas d'opérations à faire au retour d'une fonction appelée - essentiellement en transformant le retour de la fonction appelée en son propre retour. Le compilateur peut souvent effectuer quelques opérations de réparation de la pile et ensuite sauter à (plutôt qu'appeler) l'adresse de la première instruction de la fonction appelée.

L'un des avantages de cette méthode, outre l'élimination de certains appels de retour, est qu'elle permet de réduire l'utilisation de la pile. Sur certaines plates-formes ou dans le code du système d'exploitation, la pile peut être assez limitée et sur les machines avancées comme les CPU x86 de nos ordinateurs de bureau, réduire l'utilisation de la pile de cette manière améliorera les performances du cache de données.

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

L'exemple suivant montre une façon courante de faire un appel récursif qu'il serait plus difficile pour un compilateur de transformer en boucle :

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

C'est suffisamment simple pour que de nombreux compilateurs puissent le faire de toute façon, mais comme vous pouvez le voir, il y a une addition qui doit se produire après que le retour de la somme appelée renvoie un nombre, donc une simple optimisation de l'appel de queue n'est pas possible.

Si vous l'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 pourriez profiter du fait que les appels dans les deux fonctions sont des appels de queue. Ici, le travail principal de la fonction sum consiste à déplacer une valeur et à effacer un registre ou une position de la pile. La fonction sum_helper effectue toutes les opérations mathématiques.

Puisque vous avez mentionné le C++ dans votre question, je vais mentionner certaines particularités de ce langage. Le C++ vous cache certaines choses que le C ne vous cache pas. Les destructeurs sont le principal obstacle à 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 pense que les règles du C++ peuvent rendre l'optimisation plus difficile même dans les cas où la variable n'est pas nécessaire pendant la durée de l'appel, par exemple :

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

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

Une autre chose serait la conversion implicite de type, qui peut se produire en C également, mais qui est 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 queue car sum_helper retourne un double et sum devra le convertir en int.

En C++, il est assez courant de renvoyer une référence d'objet 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<< en tant que dernière instruction. cout retournera une référence à lui-même (c'est pourquoi vous pouvez enchaîner beaucoup de choses ensemble dans une liste séparée par << ), que vous forcez ensuite à être évalué comme un bool, qui finit par appeler une autre méthode de cout, operator bool(). Ce cout.operator bool() pourrait être appelé comme un appel de queue dans ce cas, mais operator<< ne pourrait pas.

EDITAR:

Une chose qui mérite d'être mentionnée est qu'une raison majeure pour laquelle 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 celui où la fonction appelante devrait s'assurer que sa valeur de retour est stockée.

Answer 4

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

Bien que vous puissiez écrire des programmes qui utilisent la récursion de queue, vous ne bénéficiez pas des avantages inhérents à la récursion de queue mis en œuvre par les compilateurs/interprètes/langages de soutien. Par exemple, Scheme prend en charge une optimisation de la récursion de queue qui transforme essentiellement la récursion en itération. Cela le rend plus rapide et invulnérable aux débordements de pile. Le C++ n'a pas une telle chose. (du moins pas dans les compilateurs que j'ai vus).

Apparemment, des optimisations de récursion de queue existent à la fois dans MSVC++ et GCC. Voir cette question pour les détails.

Answer 5

Wikipedia a un article décent sur la récursion de queue . Fondamentalement, la récursion de queue est meilleure que la récursion régulière parce qu'il est trivial de l'optimiser en 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ù il n'y a pas de boucles.

Pour le C++, il est toujours bon d'écrire vos boucles récursives avec une récursion de queue car elles peuvent être mieux optimisées, mais dans ces cas, vous pouvez généralement le faire de manière itérative en premier lieu, donc le gain n'est pas aussi grand qu'il ne le serait dans un langage fonctionnel.