Рекурсивные функции, используемые в 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 
>