Je lisais ce publier sur la récursion de la queue.
Je vais copier la solution postée: P>
unsigned int f( unsigned int a ) {
if ( a == 0 ) {
return a;
}
return f(a -1) + f( a - 1 );
}
4 Réponses :
La deuxième fonction n'est pas récursive de la queue et ne peut pas être facilement remplacée par une boucle, le plus probablement le compilateur ne le fera pas.
Ce n'est pas une récursion de la queue (où le résultat de la fonction est le résultat d'un appel récursif): il y a une opération à faire après la récursion (l'addition). Il y a une transformation plus complexe (qui dépend de la commutativité de l'addition) pour obtenir une récursion de la queue: ajoutez une fonction auxiliaire avec un accumulateur: que vous pouvez transformer en boucle puis replondifiez-le dans f
Je m'attendrais à ce que cela ne soit pas optimisé, comme mentionné par d'autres personnes, mais ces types de problèmes peuvent souvent être résolus à l'aide de la mémoire de mémoisation, qui négocie en utilisant la mémoire au lieu de faire un autre appel récursif.
Pour une belle Explication Utilisation de C ++ Vous pouvez consulter http://marknelson.us/2007/08/01/mémoisation / .
Dans votre exemple, le dernier appel pourrait être remplacé par et qui serait optimisable. Dans de nombreux cas où il apparaît que la récursion de la queue ne fonctionnera pas, il se peut que vous deviez simplement regarder votre algorithme et apporter des modifications pour aider à obtenir cette optimisation.
comme il se trouve, la récursion de la queue ne s'applique pas. Mais si vous regardez la fin du Deuxième réponse sur la question que vous avez liée, vous pouvez voir comment réécrire la fonction de manière appropriée. En commençant par
unsigned int f( unsigned int a, unsigned int multiplicative_accumulator = 1 ) {
if ( a == 0 ) {
return multiplicative_accumulator * a;
}
return f(a-1, multiplicative_accumulator * 2 );
}
Pourquoi n'utilisez-vous pas la valeur par défaut? non signé int f (non signé int a, non signé int multiplicative_accumulator = 1)
Et notez que ce code est équivalent car (a) f n'a pas d'effets secondaires, le nombre de fois que la fonction est appelée ne comporte pas, et (b) la multiplication dans non signé int est associatif et distributif à travers l'ajout. La multiplication dans float (par exemple) n'est pas associative, cette transformation n'entraînerait donc pas un code équivalent. Souvent, vous ne vous souciez pas de la différence, mais vous devez être un peu prudent avec ce genre de chose.