Posted by & filed under computación, logica, matematica, programacion.

1237116_10151782880520782_1429829332_n

Una de las primeras cosas que se suele enseñar en programación es la recursión, ya que suele ser una manera elegante y corta (no necesariamente sencilla) de resolver un problema dado. Una de las cualidades de las funciones recursivas, es que tienen una gran semejanza con la definición del algoritmo/función que estamos implementando. El ejemplo típico de una función que se da para implementar y demostrar recursión es la función que define la sucesión de Fibonacci. Por si no la conocemos la definición de Fibonacci es F(x)=F(x-1)+F(x-2), F(0) \land F(1)=1

A priori se puede ver que una implementación algorítmica de la función es:

def recursiveFibo(number):
	"""Recursive implementation of the fibonacci function"""
	if (number < 2):
		return number
	else:
		return recursiveFibo(number-1)+recursiveFibo(number-2)&#91;/sourcecode&#93;<div class="wp-git-embed" style="margin-bottom:10px; border:1px solid #CCC; text-align:right; width:99%; margin-top:-13px; font-size:11px; font-style:italic;"><span style="display:inline-block; padding:4px;">rfibo.py</span><a style="display:inline-block; padding:4px 6px;" href="https://raw.github.com/aleperno/blog/master/rfibo.py" target="_blank">view raw</a><a style="display:inline-block; padding:4px 6px; float:left;" href="https://github.com/aleperno/blog/blob/master/rfibo.py" target="_blank">view file on <strong>GitHub</strong></a></div></p>
<p style="text-align: justify;">Como vemos el código casi no difiere de la definición de la función, lo cuál lo hace más que claro y prolijo; pero <strong>en esa sencillez reside una problemática, las colisiones</strong>. Por colisiones voy a considerar los cálculos que se hacen más de una vez (no incluye F(0) ni F(1) ). Veamos un ejemplo de colisión, calculemos el fibonacci de cuatro:
F(4)=F(3)+F(2)&s=-1 y sabemos que F(3)=F(2)+F(1)&s=-1 por lo que es evidente que F(2)&s=-1 se calcula dos veces, es decir hay un cálculo innecesario.</p>
<p style="text-align: justify;">Acá es sólo una colisión, pero a medida que vamos requiriendo calcular números más grandes, habrán más y más colisiones haciendo que hagamos un uso excesivo e innecesario de poder de cálculo. Veamos que tan grande es la diferencia, para ello calculé los mismos valores con un algoritmo recursivo (el ya mostrado) y con otro iterativo más eficiente; y tomado los tiempos de ejecución. Los resultados fueron estos:</p>

<pre>Calculating the fibonacci of 4 by recursion
The fibonacci of 4 is: 3
The execution lasted: 1.09672546387e-05 seconds
-----------------------------------------------------
Calculating the fibonacci of 4 by iteration
The fibonacci of 4 is: 3
The execution lasted: 1.00135803223e-05 seconds
#####################################################
Calculating the fibonacci of 40 by recursion
The fibonacci of 40 is: 102334155
The execution lasted: 50.3286850452 seconds
-----------------------------------------------------
Calculating the fibonacci of 40 by iteration
The fibonacci of 40 is: 102334155
The execution lasted: 2.78949737549e-05 seconds</pre>
<p style="text-align: justify;">Hay que tener en cuenta que cuanto más chico el valor es menos exacto, ya que una leve variación en proporción es muy grande. En el primer caso vemos que casi no hay diferencia en ejecución, es inmediata. Pero ya queriendo calcular con 40 (un número bastante bajo) ya tarda alrededor de 50 segundos, mientras el iterativo sólo tardó 2.8 *10^{-5}=1/40000&s=-1 segundos, es decir, instantáneamente. Tenemos casi un minuto de diferencia con el algoritmo iterativo y el recursivo, producto de las colisiones que requieren más cálculos de los realmente necesarios. Es decir, <strong>queriendo calcular un número 10 veces más grande, tenemos un tiempo de cómputo 1 millones de veces mayor. Una locura no?</strong> Hagamos un análisis de cuanto más computo es necesario con el algoritmo recursivo.</p>
<p style="text-align: justify;"><a href="http://blog.aleperno.com.ar/wp-content/uploads/2013/08/1208678_10151783288180782_618804358_n.jpg"><img class="aligncenter size-full wp-image-2557" src="http://blog.aleperno.com.ar/wp-content/uploads/2013/08/1208678_10151783288180782_618804358_n.jpg" alt="1208678_10151783288180782_618804358_n" /></a></p>
<p style="text-align: center;"></p>

<h4 style="text-align: justify;"><strong><span style="text-decoration: underline;">Análisis</span></strong></h4>
<p style="text-align: justify;">El objetivo ahora es analizar cuál es la proporción que crece el cómputo cruzado (colisiones) respecto el cálculo del fibonacci de un número, para ello debemos hallar expresiones que definan ambos cálculos. Procedemos con el Fibonacci primero:</p>
<p style="text-align: justify;">f_{n}=\frac{\varphi^{n} - (1-\varphi)^{n}}{\sqrt{5}}&s=2</p>
<p style="text-align: justify;">
"Demostración"
Ahora debemos buscar la expresión para las colisiones, la misma es:</p> <p style="text-align: justify;">C_n = (\frac{5+\sqrt{5}}{10}) \varphi^{n} +(\frac{2}{5+\sqrt{5}}) (1-\varphi)^{n}, \forall n \geq 3&s=1
"Demostración"
</p> <p style="text-align: justify;">Vemos que la función de fibonacci tiene como máximo exponente n por lo que podriamos decir que necesitariamos n cómputos para un algoritmo iterativo, por ejemplo:</p> <p style="text-align: justify;">def iterativeFibo(number): list = [0,1] for i in range(2,number+1): list.append(list[i-1]+list[i-2]) return list[number]

Vemos que a la lista le agregamos una vez valores al comienzo y luego una vez por cada iteración que son n-1, es decir en total tenemos n adiciones a la lista.

Anteriormente vimos un ejemplo como el cálculo del fibonacci de 40 demoraba 2 millones de veces más con el algoritmo recursivo, que con el iterativo. Con la expresión de las colisiones, obtenemos que C_{40}=165.580.101. Recordemos que los tiempos cercanos a 0 no eran exactos pero acá vemos como era lógico que tardase 50 segundos más, si requiere casi 200 millones de cálculos extra!

Con esto espero haber podido mostrar como soluciones que a priori parecen ser elegantes y óptimas, detrás conllevan un consumo in-necesario de cómputo; haciendo la solución elegante pero ineficiente.

Nota:

Tener en cuenta las suposiciones que se hicieron a la hora de realizar los cálculos, si se quieren considerar también aquellos F(0) y F(1) la relación homogénea no cambia, cambia la particular y habría que recalcular los coeficientes con nuevas condiciones iniciales; pero el cálculo no reviste mayor complejidad del ya demostrado. No se hizo un análisis más profundo respecto a los órdenes de los algoritmos ya que no lo consideré necesario a efectos de la demostración que pretendí dar.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *