Efficacité: récursivité vs boucle

C'est juste de la curiosité de ma part, mais ce qui est plus efficace, la récursivité ou une boucle?

Donné deux fonctions (à l'aide de common lisp):

(defun factorial_recursion (x)
    (if (> x 0)
        (* x (factorial_recursion (decf x)))
        1))

(defun factorial_loop (x)
    (loop for i from 1 to x for result = 1 then
        (* result i) finally
        (return result)))

Qui est plus efficace?

source d'informationauteur SpaceFace

27

Je n'ai même pas à lire votre code.

Boucle est plus efficace pour les factorielles. Lorsque vous faites la récursivité, vous avez jusqu'à x appels de fonction sur la pile.

Vous presque jamais utiliser la récursivité pour des raisons de performances. Vous utiliser la récursivité pour rendre le problème plus simple.
9

Mu.

Sérieusement maintenant, il n'a pas d'importance. Pas pour des exemples de cette taille. Ils ont tous deux la même complexité. Si votre code n'est pas assez rapide pour vous, c'est probablement l'un des derniers endroits que vous regarde.

Maintenant, si vous voulez vraiment savoir qui est plus rapide, les mesurer. Sur SBCL, vous pouvez appeler chaque fonction dans une boucle et de mesurer le temps. Puisque vous avez deux fonctions simples, est assez. Si votre programme a été plus compliqué, un profiler serait plus utile. Astuce: si vous n'avez pas besoin d'un générateur de profils pour vos mesures, vous n'avez probablement pas besoin de vous soucier de la performance.

Sur ma machine (SBCL 64 bits), j'ai couru à vos fonctions et obtenu ceci:
```
CL-USER> (time (loop repeat 1000 do (factorial_recursion 1000)))
Evaluation took:
  0.540 seconds of real time
  0.536034 seconds of total run time (0.496031 user, 0.040003 system)
  [ Run times consist of 0.096 seconds GC time, and 0.441 seconds non-GC time. ]
  99.26% CPU
  1,006,632,438 processor cycles
  511,315,904 bytes consed

NIL
CL-USER> (time (loop repeat 1000 do (factorial_loop 1000)))
Evaluation took:
  0.485 seconds of real time
  0.488030 seconds of total run time (0.488030 user, 0.000000 system)
  [ Run times consist of 0.072 seconds GC time, and 0.417 seconds non-GC time. ]
  100.62% CPU
  902,043,247 processor cycles
  511,322,400 bytes consed

NIL
```
Après la mise de vos fonctions dans un fichier avec (declaim (optimize speed)) en haut, la récursivité temps a chuté à 504 millisecondes et le temps de boucle est tombé à 475 millisecondes.

Et si vous voulez vraiment savoir ce qu'il se passe, essayez de dissasemble sur vos fonctions et de voir ce qui est là.

Encore une fois, cela ressemble à un non-problème pour moi. Personnellement, j'essaie d'utiliser Common Lisp comme un langage de script pour le prototypage, puis profil et d'optimiser les pièces qui sont lents. L'obtention de 500ms à 475ms n'est rien. Par exemple, dans certains code personnel, j'ai eu quelques ordres de grandeur de l'accélération par le simple ajout d'un type d'élément à un tableau (le tableau de stockage de 64 fois plus petit dans mon cas). Bien sûr, en théorie, il aurait été plus rapide de réutiliser array (après les rendant plus petites) et de ne pas allouer plus de et plus. Mais simplement en ajoutant :element-type bit elle était assez pour que ma situation - plus de changements auraient besoin de plus de temps pour très peu d'avantage supplémentaire. Peut-être que je suis bâclée, mais "rapide" et "lent" ne signifie pas grand-chose pour moi. Je préfère le "fast enough" et "trop lent". Les deux fonctions sont "assez rapide" dans la plupart des cas (ou les deux sont "trop lent" dans certains cas) donc il n'y a pas de réelle différence entre eux.
8

Si vous pouvez écrire des fonctions récursives en telle sorte que l'appel récursif est la dernière chose fait (et la fonction est donc récursives terminales) et le langage et le compilateur/interpréteur que vous utilisez prend en charge la queue de la récursivité, alors la fonction récursive peut (généralement) être optimisée dans le code qui est vraiment itératif, et est aussi rapide qu'une version itérative de la même fonction.

Sam je Suis est correcte bien que, itératif fonctions sont généralement plus rapides que leurs récursive homologues. Si une fonction récursive est d'être rapide comme un processus itératif de la fonction qui fait la même chose, vous devez compter sur l'optimiseur.

La raison pour cela est qu'un appel de fonction est beaucoup plus cher qu'un saut, plus vous consommez de l'espace de pile, un (très) ressource finie.

La fonction que vous donnez n'est pas la queue récursive parce que vous appelez factorial_recursion et puis vous multipliez par x. Un exemple d'une queue-une version récursive serait
```
(defun factorial-recursion-assist (x cur)
    (if (> x 1)
        (factorial-recursion-assist (- x 1) (+ cur (* (- x 1) x)))
        cur))

(defun factorial-recursion (x)
    (factorial-recursion-assist x 1))

(print (factorial-recursion 4))
```

-2

Voici une queue-factorielle récursive (je pense):

(defun fact (x)
  (funcall (alambda (i ret)
             (cond ((> i 1)
                    (self (1- i) (* ret i)))
                   (t
                    ret)))
           x 1))

Vous devez vous connecter pour publier un commentaire.