les frais généraux récursion - Est-ce grave? [dupliquer]

Question

  

Possible en double:    est récursion toujours plus rapide que le bouclage?

J'a d'abord été formés au programme sérieux en C, il y a environ 15 ans. Mon employeur voulait un code hautement optimisé pour les tâches difficiles informatiquement. Je me souviens avoir été informé plus d'une fois de réécrire récurrences comme des boucles, même à la coûteuse de la lisibilité, afin d'éviter les « frais généraux de récursivité. » Comme je l'ai bien compris alors, les frais généraux de récursivité l'effort supplémentaire nécessaire pour pousser des données sur une pile et pop plus tard au large.

Maintenant, je code en C, Python, Perl, Java et parfois, et je me demande parfois de récurrences. Est-il encore quelque chose à gagner en les réécrivant? Que faire s'ils sont récurrences de la queue? Ont des compilateurs modernes fait toutes ces questions sans intérêt? Ces préoccupations sont non pertinentes pour les langues interprétées?

Answer 1

Recursion peut conduire à une surcharge significative si le noyau de la fonction récursive est moins cher que le calcul du code d'entrée de fonction / sortie et le coût de l'appel lui-même. La meilleure façon de savoir est tout simplement au profil deux versions du code -. Récursive, et un pas

Cela dit, si votre idée d'éviter la récursivité est de faire une structure semblable à pile vous-même, attention - il peut ne pas être forcément plus rapide que l'approche récursive plus simple. Encore une fois, le profilage est votre ami.

Enfin, rappelez-vous que le temps de programmeur est plus cher que le temps CPU. Avant de micro-optimiser votre code, il est vraiment une bonne idée de mesurer pour voir si elle sera vraiment un problème.

Answer 2

Il est grave. La plupart des langues que je code dans ont un coût réel pour fonctionner des appels (les compilateurs pour eux peuvent généralement faire la queue récursion, si bien que parfois ce n'est pas un problème).

Ce coût, et le fait que la pile n'est pas une ressource illimitée, me fait généralement tendance à utiliser uniquement récursion pour les cas où je sais qu'il ya une limite à la profondeur, il peut aller.

Par exemple, je sais une recherche d'arbre binaire équilibré n'aller cinquante niveaux de profondeur pour une quadrillions entrées. Je ne veux pas, cependant, utilisez:

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

depuis le faire pour n de vingt millions ne serait pas sain pour une pile.

Answer 3

Le problème existe toujours. Récursion prend beaucoup d'espace de pile, comme chaque fois qu'une méthode elle-même appelle, un pointeur vers et ses variables locales sont générées à nouveau. Le nombre d'appels de fonction effectués au cours de la récursion fait une utilisation de mémoire O (n); par rapport à O (1) d'une fonction non récursif comme des boucles.

Answer 4

Je ne pense pas que l'une des langues que vous avez mentionnées besoin que les outils plate-forme / compilateur queue élimination appel . Vous pouvez trouver des langues que ne nécessitent cette optimisation -. Les langues les plus fonctionnels ont cette exigence

Cependant, une autre chose que vous devez considérer est que les ordinateurs sont devenus des ordres de grandeur plus rapidement qu'ils ne l'étaient il y a 15 ans, il est donc beaucoup plus rare maintenant, alors avant que vous devez vous soucier de micro-optimisations. Un programme qui il y a 15 ans aurait pu nécessiter l'optimisation de la main attention en assembleur pour obtenir des performances décentes pourrait fonctionner incroyablement rapide sur un ordinateur moderne, même si elle était écrite dans un langage de haut niveau comme Java. Cela ne veut pas dire que la performance est jamais un problème plus - mais vous devriez vous concentrer sur le choix du algorithme correct et sur l'écriture lisibles code. Seulement faire des micro-optimisations après avoir mesuré les performances et vous pouvez voir que le code en question est le goulot d'étranglement.

Une chose que vous faire besoin de s'inquiéter si la pile déborde. S'il y a un risque que cela se produise, il pourrait être utile de réécrire une fonction récursive de manière itérative à la place.

Answer 5

Les gens disent beaucoup de choses sur les performances stupides.

1. Si vous besoin récursion, comme faire en profondeur d'abord arbre de marche, alors vous avez besoin, donc l'utiliser.

2. Avant de se soucier de la performance de quoi que ce soit , savoir si vous avez un problème et où il est.
   Les problèmes de performance sont comme les escrocs et des tricheurs - ils se spécialisent dans d'être là où on ne s'y attend, donc si vous êtes inquiet au sujet quelque chose de spécifique comme récursion, vous êtes presque assuré d'être se soucier de la mauvaise chose

.

A mon avis, la meilleure façon de trouver des problèmes de performance est par échantillonnage de la pile à temps-horloge murale , et examiner les échantillons pour voir ce que le programme fait , non seulement en obtenant des mesures et je me demandais ce qu'ils veulent dire.

Cela dit, si vous ne trouvez 10% ou plus du temps qui passe dans un appel récursif, et rien ne se passe beaucoup reste à l'intérieur de la routine récursive, et vous pouvez la boucle, puis en boucle, il sera probablement aider.