recursividad - ¿Las funciones recursivas son usadas en R?

recursividad ejemplos

Question

La función canónica para demostrar la recursión es la función factorial (). Intenté una implementación simple de mí mismo y se me ocurrió esto:

factorial <- function(x){

if(x==1)
    return( 1)
else
    return(x*factorial(x-1))

}

De mi estudio del tema, parece haber cierto debate acerca de si es mejor usar la recursión o la iteración simple. Quería ver cómo lo implementa R y encontré una función factorial () en el paquete gregmisc. Pensé que encontraría algo como mi implementación o una iteración regular. Lo que encontré esto:

> factorial
function (x) 
gamma(x + 1)
<environment: namespace:base>

Así que la respuesta a mi pregunta de si R prefiere la recursión o la iteración es "ninguno". Al menos en esta implementación. ¿Se evitan las funciones recursivas en R por una buena razón?

Actualizar:

versión gregmisc:

>ptm <- proc.time()
> factorial(144)
[1] 5.550294e+249
> proc.time() - ptm
   user  system elapsed 
  0.001   0.000   0.001 

mi version:

> factorial(144)
[1] 5.550294e+249
> proc.time() - ptm
  user  system elapsed 
  0.002   0.001   0.006 

Answer 1

Creo que la forma más natural de expresar cálculos matemáticos en R es a través de la notación matemática / estadística. El objetivo principal del lenguaje es facilitar la expresión de cálculos estadísticos de una manera natural.

Su propio ejemplo de factorial implementado usando gamma encaja muy bien con esta vista. No sé cómo se implementa gamma , pero no necesitamos saberlo para poder utilizar R. Como usuario, lo más importante es obtener la respuesta correcta. Si el código demuestra ser prohibitivamente lento, es cuando optimizas. El primer lugar para comenzar sería nuevamente las matemáticas y la elección del algoritmo, no los detalles de la implementación.

David Heffernan tiene razón en que la recursión suele ser más lenta que la iteración, pero lo que no parece considerar es que rara vez importa. Usando su propio ejemplo, los números de Fibonacci, lo realmente importante es evitar volver a calcular los números, lo que se puede hacer a través de la memorización. Esto hace que el cálculo se ejecute en tiempo lineal en lugar de exponencial, una gran mejora. Una vez que haya hecho eso, todavía puede obtener una pequeña mejora implementando el algoritmo usando un bucle, pero entonces probablemente no importa. Además, hay una forma cerrada .

Tanto la función factorial como los números de fibonacci también crecen muy rápidamente. Esto significa que cada operación aritmética (adiciones, multiplicaciones, etc.) comenzará a tomar mucho tiempo, mientras que la recursión no se vuelve más costosa o al menos no tan rápido. Una vez más, las consideraciones matemáticas superan los detalles de la implementación.

TL; DR

Mi consejo es:

1. Escribe el algoritmo de la manera más simple posible.
2. Asegúrese de que es correcto.
3. Si y solo si el algoritmo es demasiado lento en una entrada realista:
   1. Averigüe qué parte del algoritmo está tomando el tiempo / lo que es la complejidad del tiempo.
   2. Arregla esa parte y solo esa parte.
   3. Repita el proceso si es necesario.

Answer 2

La respuesta es sí. Las funciones recursivas se usan en R. Mientras que gran parte de R está escrita en R, algunas rutinas altamente optimizadas son envoltorios a C o FORTRAN. Además, gran parte de R-BASE es primitiva. Básicamente, las rutinas rápidas donde es más probable que se use la recursión es menos probable que se las vea, a menos que alguien realmente mire los binarios.

Un buen ejemplo de una función recursiva es probablemente la función más utilizada de todas:

> 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 
> 

Answer 3

Para el cálculo del factorial entero, la implementación recursiva es más lenta y más compleja. Invariablemente, la iteración se utiliza en el código de producción.

La función factorial que se refiere está en el paquete base. Opera en valores reales en lugar de enteros, de ahí esa implementación. Su documentación establece:

factorial (x) (x! para entero no negativo x) se define como gamma (x + 1)

Un ejemplo más interesante es el código para implementar la serie Fibonnaci, que es extraordinariamente inútil cuando se implementa con una recursión ingenua. El enfoque recursivo se puede hacer eficiente a través de la memoria, pero siempre se prefiere una iteración simple si el desempeño está en juego.

Otro algoritmo común que se expresa naturalmente de manera recursiva es Quicksort. Esto, como todos los algoritmos, puede implementarse sin recursión, pero es bastante complejo hacerlo. Hay poco beneficio en el uso de un Quicksort no recursivo, por lo que es común usar la implementación ingenua recursiva.

La recursión es una buena opción de implementación:

• si el rendimiento no se ve comprometido, y
• si es más natural (por lo tanto, más fácil de verificar y mantener) implementarlo recursivamente.