Это просто любопытство с моей стороны, но что более эффективно, рекурсия или цикл?
Для двух функций (с использованием общего 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)))
Что более эффективно?
Мне даже не нужно читать ваш код.
Loop более эффективен для факториалов. Когда вы выполняете рекурсию, у вас есть до x вызовов функций в стеке.
Вы почти никогда не используете рекурсию по соображениям производительности. Вы используете рекурсию, чтобы сделать проблему более простой.
Mu.
Серьезно сейчас, это не имеет значения. Не для примеров такого размера. Они оба имеют одинаковую сложность. Если ваш код недостаточно быстрый для вас, это, вероятно, одно из последних мест, на которые вы бы посмотрели.
Теперь, если вы действительно хотите узнать, что быстрее, измерьте их. В SBCL вы можете вызывать каждую функцию в цикле и измерять время. Поскольку у вас есть две простые функции, time достаточно. Если ваша программа была более сложной, профилировщик был бы более полезен. Подсказка: если вам не нужен профайлер для ваших измерений, вам, вероятно, не нужно беспокоиться о производительности.
На моей машине (SBCL 64 бит) я выполнил ваши функции и получил следующее:
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
После ввода ваших функций в файл с (declaim (optimize speed)) вверху время рекурсии упало до 504 миллисекунд, а время цикла снизилось до 475 миллисекунд.
И если вы действительно хотите знать, что происходит, попробуйте dissasemble в своих функциях и посмотреть, что там.
Опять же, это выглядит как не проблема для меня. Лично я пытаюсь использовать Common Lisp, как язык сценариев для прототипирования, затем профиль и оптимизацию медленных частей. Получение от 500 мс до 475 мс - ничто. Например, в каком-то личном коде я получил несколько порядков ускорения, просто добавив тип элемента в массив (таким образом, хранилище массивов в 64 раза меньше в моем случае). Конечно, теоретически было бы быстрее повторно использовать этот массив (после его уменьшения) и не выделять его снова и снова. Но просто добавив :element-type bit для этого был достаточно для моей ситуации - больше изменений потребовало бы больше времени для очень небольшой дополнительной выгоды. Может быть, я неаккуратный, но "быстрый" и "медленный" для меня мало что значит. Я предпочитаю "достаточно быстро" и "слишком медленно". В большинстве случаев обе ваши функции "достаточно быстры" (или в некоторых случаях "слишком медленны"), поэтому между ними нет никакой реальной разницы.
Если вы можете записывать рекурсивные функции таким образом, чтобы рекурсивный вызов был последним (и функция, таким образом, была рекурсивной), а язык и компилятор/интерпретатор, которые вы используете, поддерживают хвостовую рекурсию, тогда рекурсивная функция может ( обычно) оптимизируется на код, который действительно является итеративным, и работает так же быстро, как итеративная версия той же функции.
Сам Сэм Я прав, хотя итеративные функции обычно быстрее, чем их рекурсивные аналоги. Если рекурсивная функция должна быть такой же быстрой, как итеративная функция, которая делает то же самое, вам приходится полагаться на оптимизатора.
Причина этого в том, что вызов функции намного дороже, чем скачок, плюс вы потребляете пространство стека, (очень) конечный ресурс.
Функция, которую вы даете, не является рекурсивной, поскольку вы вызываете factorial_recursion а затем умножаете ее на x. Примером рекурсивной версии будет
(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))
Здесь хвосто-рекурсивный факторный (я думаю):
(defun fact (x)
(funcall (alambda (i ret)
(cond ((> i 1)
(self (1- i) (* ret i)))
(t
ret)))
x 1))