Ich muss Ihren Code nicht einmal lesen.
Schleife ist effizienter für Faktoren. Wenn Sie Rekursion durchführen, haben Sie bis zu x Funktionsaufrufe auf dem Stapel.
Sie verwenden Rekursion fast nie aus Leistungsgründen. Sie verwenden Rekursion, um das Problem zu vereinfachen.
Mu.
Im Ernst, es spielt keine Rolle. Nicht für Beispiele dieser Größe. Sie haben beide die gleiche Komplexität. Wenn Ihr Code nicht schnell genug für Sie ist, ist dies wahrscheinlich einer der letzten Orte, die Sie sich ansehen.
Wenn Sie jetzt wirklich wissen möchten, welche schneller ist, messen Sie sie. Auf SBCL können Sie jede Funktion in einer Schleife aufrufen und die Zeit messen. Da Sie zwei einfache Funktionen haben, ist time ausreichend. Wenn Ihr Programm komplizierter wäre, wäre ein Profiler nützlicher. Hinweis: Wenn Sie für Ihre Messungen keinen Profiler benötigen, müssen Sie sich wahrscheinlich keine Gedanken über die Leistung machen.
Auf meinem Rechner (SBCL 64 Bit) habe ich Ihre Funktionen ausgeführt und folgendes bekommen:
%Vor% Nachdem Sie Ihre Funktionen in eine Datei mit (declaim (optimize speed)) am oberen Rand eingefügt hatten, fiel die Rekursionszeit auf 504 Millisekunden und die Schleifenzeit auf 475 Millisekunden.
Und wenn Sie wirklich wissen wollen, was vor sich geht, versuchen Sie dissasemble auf Ihre Funktionen und sehen, was da drin ist.
Auch das sieht für mich wie ein Nicht-Problem aus. Persönlich versuche ich, Common Lisp wie eine Skriptsprache für das Prototyping zu verwenden, um dann die langsamen Teile zu profilieren und zu optimieren. Von 500ms auf 475ms zu kommen, ist nichts. Zum Beispiel habe ich in einem persönlichen Code einige Größenordnungen beschleunigt, indem ich einfach einen Elementtyp zu einem Array hinzufügte (wodurch der Array-Speicher in meinem Fall 64 Mal kleiner wurde). Sicher, in der Theorie wäre es schneller gewesen, dieses Array wiederzuverwenden (nachdem es kleiner gemacht wurde) und es nicht immer wieder zuzuteilen. Aber einfach :element-type bit hinzuzufügen war genug für meine Situation - mehr Änderungen hätten mehr Zeit für sehr wenig zusätzlichen Nutzen erfordert. Vielleicht bin ich schlampig, aber "schnell" und "langsam" bedeuten mir nicht viel. Ich bevorzuge 'schnell genug' und 'zu langsam'. Beide Funktionen sind in den meisten Fällen "schnell genug" (oder beide sind in manchen Fällen "zu langsam"), so dass es keinen wirklichen Unterschied zwischen ihnen gibt.
Wenn Sie rekursive Funktionen so schreiben können, dass der rekursive Aufruf ist, ist die allerletzte Sache (und die Funktion ist also tail-recursive ) und die Sprache und der Compiler / Interpreter, den Sie verwenden, unterstützt die Tail-Rekursion, dann kann die rekursive Funktion (normalerweise) zu wirklich iterativem Code optimiert werden und ist so schnell wie eine iterative Version der gleichen Funktion.
Sam I Am ist jedoch korrekt, iterative Funktionen sind normalerweise schneller als ihre rekursiven Gegenstücke. Wenn eine rekursive Funktion so schnell sein soll wie eine iterative Funktion, die dasselbe tut, müssen Sie sich auf den Optimierer verlassen.
Der Grund dafür ist, dass ein Funktionsaufruf viel teurer ist als ein Sprung, und Sie verbrauchen Stack-Speicherplatz, eine (sehr) endliche Ressource.
Die von Ihnen angegebene Funktion ist nicht rekursiv, da Sie factorial_recursion aufrufen und dann mit x multiplizieren. Ein Beispiel für eine tail-rekursive Version wäre
Tags und Links performance recursion common-lisp