Recursividad terminal en R

Ayer estuve “jugando” a lo largo del día con unos ejemplos de ejercicios en R que pululaban por mis apuntes de la carrera.
Todo iba según lo previsto hasta el ejemplo sobre la sucesión de Fibonacci porque está implementada forma directa, pero ya sabemos que esa no es la forma más eficiente. Voy a reescribirlo, aunque ya hice lo mismo una vez en Ocaml. Incluyo mis palabras como comentarios en R, para que se pueda copiar y pegar directamente a la consola y probarlo, así como la explicación sobre la complejidad y el tiempo de cómputo necesario.

## Solución propuesta en los apuntes
## Definiendo una función recursiva:

f < - function(n) {
if (n<=2) {
a <- 1
} else {
a <- f(n-1) + f(n-2)
}
return(a)
}

## Resultados para los primeros 20 números
for (i in 1:20) {
print(f(i))
}

## Mostrar el tiempo empleado en realizar f(20)
system.time( f(20) )
## En mi máquina el tiempo necesario es de apenas 0.22s

## Mostrar el tiempo empleado en realizar f(20)
system.time( f(30) )
## En mi máquina el tiempo necesario es de 27.30s

## Si el programa se imprementa de forma puramente recursiva, la ejecución
## será inviable conforme el número de la sucesión a calcular vaya aumentando.
## Una llamada debe esperar a que sus llamadas "hijas" terminen para sumar,
## pero las llamadas hijas tienen a su vez otras dos llamadas hijas cada una.
## El proceso genera un árbol enorme de llamadas que eventualmente satura
## la pila de la memoria, degradando el rendimiento de la máquina o incluso
## bloqueandola

## Solución propuesta
## Empleamos una función recursiva terminal que se llama a si misma, pero
## que no necesita esperar a que otra instancia termine de hacer cálculos.
## La función Fib recibe el número a calcular
## Si es mayor que 2, se pasa a una función f, que afortunadamente no
## sobreescribe a la f de los apuntes (ocultacion).
## La funcion f no necesita esperar a otras llamadas, pues tiene 3 parametros
## i == es el numero de quien calculamos fib
## j == es el fib de i-1
## k == es el fib de i-2
## Los resultados se van pasando de una iteración a la siguiente, no acarreando
## llamadas que los vuelvan a calcular. Tampoco hace llamadas duplicadas.
## En lugar de calcular el Fib de n y hacer llamadas para el Fib de los numeros
## anteriores a n, empezamos desde el 3 y vamos aumentando i
## Esto simula como calcularía una persona el Fibonacci con lápiz y papel

Fib <- function (n){
if (n<=2) {
resultado <- 1
} else {
i <- 2; j <- 1; k <- 0;
f <- function (i,j,k){
if (i == n){
return (j+k)
} else {
return (f(i+1,j+k,j))
}
}
resultado <- f(i,j,k)
}
return (resultado)
}

## El tiempo empleado en calcular Fib(20) y Fib(30)
system.time(Fib(20))
system.time(Fib(30))
## En ambos casos, el tiempo necesario fue 0.00s

## Complejidad de cálculo:
## Dado un numero n de la sucesión de Fibonacci, el cociente (n+1)/n es
## 1.61803398874… (número aureo)
## Con mi pc como referencia, el n=30 toma 27.3s para ser calculado por
## la vía tradicional. El tiempo necesario para calcular otro número:
## (complejidad ^ diferencia entre numeros) * (tiempo de referencia)

## De modo que calcular f(40) tardaría...
## (1.61803398874 ^ 10) * 27.3
## = 3357.678 segundos
## es decir 56 minutos

## Pero es peor querer calcular el f(100), porque la complejidad se eleva a 70 y...
## (1.61803398874 ^ 70) * 27.3
## = 1.162244e+16 segundos
## que son unos muy poco prácticos 368293027 años y pico

Por cierto, en Ocaml y con mi anterior PC los números eran igualmente bizarros pero me ha sorprendido muchísimo la diferencia de rendimiento entre ambos lenguajes, incluso cuando el ejemplo con Ocaml lo realicé sobre una máquina notablemente inferior a la que tengo ahora 🙂

Anuncios

Un comentario sobre “Recursividad terminal en R

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s