Рекурсивные функции, используемые в R?
Каноническая функция для демонстрации рекурсии - это функция факториала(). Я попробовал простую реализацию этого сам и придумал это:
factorial <- function(x){
if(x==1)
return( 1)
else
return(x*factorial(x-1))
}
Из моего обзора темы, по-видимому, есть некоторые споры о том, лучше ли использовать рекурсию или простое итерацию. Я хотел увидеть, как R реализует его и нашел функцию factorial() в пакете gregmisc. Я думал, что найду что-то вроде моей реализации или вместо обычной итерации. Что я нашел это:
> factorial
function (x)
gamma(x + 1)
<environment: namespace:base>
Таким образом, ответ на мой вопрос о том, предпочитает ли R рекурсия или итерация, "ни". По крайней мере, в этой реализации. Являются ли рекурсивные функции исключенными в R по уважительной причине?
Update:
версия gregmisc:
>ptm <- proc.time()
> factorial(144)
[1] 5.550294e+249
> proc.time() - ptm
user system elapsed
0.001 0.000 0.001
моя версия:
> factorial(144)
[1] 5.550294e+249
> proc.time() - ptm
user system elapsed
0.002 0.001 0.006
Ответы
Ответ 1
Для вычисления целочисленного факториала рекурсивная реализация медленнее и сложнее. Неизменно, итерация используется в производственном коде.
Функция factorial
, на которую вы ссылаетесь, находится в базовом пакете. Он работает с реальными значениями, а не с целыми числами, следовательно, с реализацией. В его документации указано:
factorial (x) (x! для неотрицательных целое число x) определяется как гамма (x + 1)
Более интересным примером является код для реализации серии Fibonnaci, который необычайно расточителен при реализации с наивной рекурсией. Рекурсивный подход может быть эффективен с помощью memoization, но простая итерация всегда должна быть предпочтительной, если на карту поставлена производительность.
Другим распространенным алгоритмом, который выражается естественным образом рекурсивным образом, является Quicksort. Это может, как и все алгоритмы, быть реализованы без рекурсии, но это довольно сложно сделать. Существует мало преимуществ в использовании нерекурсивного Quicksort, поэтому он обычно использует наивную рекурсивную реализацию.
Рекурсия - хороший выбор реализации:
- если производительность не скомпрометирована, а
- если это более естественно (следовательно, проще проверить и поддерживать) для реализации рекурсивно.
Ответ 2
Я думаю, что наиболее естественным способом выразить математические вычисления в R является математическое/статистическое обозначение. Вся суть языка состоит в том, чтобы облегчить выражение статистических вычислений естественным образом.
У вас есть пример factorial
, который реализуется с помощью gamma
, прекрасно подходит для этого представления. Я не знаю, как реализуется gamma
, но нам не нужно знать, что для использования R. Как пользователь, самое главное, чтобы получить правильный ответ. Если код оказывается непомерно медленным, то есть когда вы оптимизируете. Первое место для начала - это математика и выбор алгоритма, а не детали реализации.
Дэвид Хеффернан прав, что рекурсия обычно медленнее, чем итерация, но то, что он, похоже, не считает, - это редко. Используя свой собственный пример чисел Фибоначчи, действительно важно избегать пересчета чисел, что может быть сделано посредством запоминания. Это приводит к тому, что вычисление выполняется в линейном времени вместо экспоненциального времени - огромное улучшение. Как только вы это сделаете, вы все равно можете получить небольшое улучшение, выполнив алгоритм с использованием цикла, но тогда это, вероятно, не имеет значения.
Кроме того, существует закрытая форма .
И факториальная функция, и число фибоначчи также растут очень быстро. Это означает, что каждая арифметическая операция (добавления, умножения и т.д.) Начнет длиться долго, а рекурсия не станет дороже или, по крайней мере, не так быстро. Опять же, математические соображения о деталях реализации козыря.
TL; DR
Мой совет:
- Запишите алгоритм самым простым способом.
- Убедитесь, что это правильно.
- Если и только если алгоритм слишком медленный на реалистичном входе:
- Узнайте, какая часть алгоритма занимает время/что такое временная сложность.
- Исправьте эту часть и только ту часть.
- При необходимости повторите процесс.
Ответ 3
Ответ: да, рекурсивные функции используются в R. Хотя большая часть R сама записывается в R, некоторые высоко оптимизированные подпрограммы являются обертками для C или FORTRAN. Кроме того, большая часть R-BASE является примитивной. В принципе, быстрые процедуры, в которых рекурсия, скорее всего, будет использоваться, будут наименее вероятными, если кто-то действительно не просмотрит двоичные файлы.
Хорошим примером рекурсивной функции является, вероятно, наиболее часто используемая функция для всех:
> c
function (..., recursive = FALSE) .Primitive("c")
> set.seed(1)
> x <- list('a'=list(1:2, list(rnorm(10)), 'b'=rnorm(3)))
> c(x)
$a
$a[[1]]
[1] 1 2
$a[[2]]
$a[[2]][[1]]
[1] -0.6264538 0.1836433 -0.8356286 1.5952808 0.3295078 -0.8204684 0.4874291 0.7383247
[9] 0.5757814 -0.3053884
$a$b
[1] 1.5117812 0.3898432 -0.6212406
> c(x, recursive=TRUE)
a1 a2 a3 a4 a5 a6 a7 a8
1.0000000 2.0000000 -0.6264538 0.1836433 -0.8356286 1.5952808 0.3295078 -0.8204684
a9 a10 a11 a12 a.b1 a.b2 a.b3
0.4874291 0.7383247 0.5757814 -0.3053884 1.5117812 0.3898432 -0.6212406
>