Fibonacci recursivo en C [ intentemos no repetir operaciones! ]

Es un ejercicio muy típico cuando se está aprendiendo con funciones recursivas es la sucesión de Fibonacci, aquella en la que F(n)=F(n-1)+F(n-2).
Aunque esta técnica podemos (y deberíamos) utilizarla para una gran cantidad de algoritmos. A veces es necesario sacrificar un poco la memoria del sistema (sin pasarnos) para agilizar y hacer más rápido el programa. Debemos adoptar una solución que beneficie al usuario, no es plan de dejarlo sin memoria, pero tampoco es plan de que la solución se eternice.

Una primera implementación puede ser la siguiente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int fibonacci_simple(int n)
{
/* La función normal, recursiva */
if (n>2)
return fibonacci_simple(n-1) + fibonacci_simple(n-2);
/* Este es el caso más común, */
else if (n==2) /* Ponemos esto para agilizar un poco el proceso */
return 1;
else if (n==1)
return 1;
else if (n==0)
return 0;
else
return -1; /* Error */
}

Si creamos un programa de ejemplo como este:

1
2
3
4
5
6
7
8
9
10

int main(int argc, char *argv[])
{
unsigned int numero;

/* Generamos Fibonaccis */
for (numero=0; numero<48; numero++)
printf("%u\n", fibonacci_simple(numero));

return 0;
}

Podemos observar que para generar la secuencia de 48 números (he escogido este valor, porque a partir de ahí no tenemos suficiente de 32bits para almacenar el valor obtenido), tardamos varios minutos, en concreto, en mi equipo (Pentium M 1.73MHz), echó algo más de 10 minutos. ¡ 10 minutos ! Es un buen rato para lo que ha hecho.
Si lo estudiamos detenidamente (en negrita pongo las veces que llamamos a fibonacci_simple() sin necesidad):

fibonacci_simple(0)
fibonacci_simple(1)
fibonacci_simple(2)
fibonacci_simple(3) (que llama a fibonacci_simple(2) y fibonacci_simple(1) )
fibonacci_simple(4) (que llama a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) ) y a fibonacci_simple(2) )
fibonacci_simple(5) (que llama a fibonacci_simple(4) ( que llama a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) ) y a fibonacci_simple(2) ) y a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) )

Yo creo que con esto nos hacemos una idea de lo que quiero decir, se repiten demasiadas operaciones, seguro que hay alguna forma de solucionar esto.

Propongo lo siguiente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

int fibonacci_buffer(int n)
{
static int *fbuffer=NULL; /* Buffer */
static int bufsize=0; /* Tamaño de buffer */
int n3; /* n-2 */
int i; /* Recorre buffers */

if (n>2)
{
n3=n-2;
if (fbuffer==NULL)
{
fbuffer = (int*) malloc((n3 * sizeof(int)));
for (i=0; i<n3; i++)
fbuffer[i]=0; /* Ponemos buffer a 0 */

/* printf("Creo buffer: %d -- %d\n", n3*sizeof(int), errno); */

bufsize=n3;
}
else if (bufsize<n3)
{
fbuffer = (int*) realloc(fbuffer, n3 * sizeof(int));
/* printf("Amplio buffer\n"); */

for (i=bufsize; i<n3; i++) /* Ponemos a 0 la memoria nueva */
fbuffer[i]=0;

bufsize=n3;
}
/* printf("-%d--%d\n", n, fbuffer[n3-1]); */
if (fbuffer[n3-1]!=0) /* Si se encuentra el fibonacci del número que buscamos */
return fbuffer[n3-1]; /* en memoria, lo devolvemos directamente */
else
{
/* Si el fibonacci no se encuentra, vamos a generarlo */
fbuffer[n3-1] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2);
// printf("He generado con éxito fbuffer[%d]\n", n3-1);
return fbuffer[n3-1];
}

/* return fibonacci_simple(n-1) + fibonacci_simple(n-2); */
}
else if (n==2) /* Ponemos esto para agilizar un poco el proceso */
return 1;
else if (n==1)
return 1;
else if (n==0)
return 0;
else if (n==-1) /* Un caso nuevo n==-1 */
free(fbuffer); /* Liberamos memoria */

return -1; /* Error */
}

Es algo más enrevesado, ya que usamos variables estáticas (podríamos hacer variables globales, con cuidado), así evitamos que la información que vamos almacenando se pierda entre ejecuciones de la función; por otra parte, utilizamos malloc() y realloc() para reservar sólo la memoria que vamos necesitando.
Por otra parte para reducir la memoria utilizada, hacemos que fibonacci(3) se almacene en la posición 0 del buffer (porque el de 2, 1 y 0, ya nos los sabemos); por otra parte… la variable n3 vale n-2; esto es simplemente porque si tenemos que calcular fibonacci(5), y sabemos que fibonacci(3) está almacenado en fbuffer[0], fibonacci(4) estará en fbuffer[1] y fibonacci(5) estará en fbuffer[2]; es decir tenemos que almacenar 3 valores de fibonacci (5-2=3).
Por otra parte, siempre que reservamos memoria ponemos los nuevos espacios a 0, ya que comprobamos que no hay ningún valor almacenado si éstos son 0.

Con el almacén de los números conseguimos que el esquema anterior se quede en:

fibonacci_buffer(0)
fibonacci_buffer(1)
fibonacci_buffer(2)
fibonacci_buffer(3) (que llama a fibonacci_buffer(2) y fibonacci_buffer(1)
fibonacci_buffer(4) (que llama a fibonacci_buffer(3) ( que saca el valor del buffer ) y a fibonacci_simple(2) )
fibonacci_buffer(5) (que llama a fibonacci_buffer(4) (que saca el valor del buffer) y a fibonacci_buffer(3) (que saca el valor del buffer)

Con este algoritmo consigo generar todos los números en 4ms.

¿Será posible simplificarlo un poco más?
Sólo hay que ver cómo se hace la generación de valores de forma recursiva. Si lo pensamos bien, cuando llamamos a fibonacci_buffer(5) la primera vez y lo queremos almacenar en fbuffer[2] llamaremos a fibonacci_buffer(4) (que se almacenará en fbuffer[1], y éste llamará a fibonacci_buffer(3) (que se almacenará en fbuffer[0]); es decir, lo primero que se generará será fbuffer[0], luego fbuffer[1] y por último fbuffer[2]… ¡ vamos por orden ! Sabiendo esto, nos podremos ahorrar el código de poner a 0 los elementos del buffer sabiendo cuál es el último elemento generado.

Para los incrédulos, podemos eliminar el comentario de la línea:

1	// printf("He generado con éxito fbuffer[%d]\n", n3-1);

y ejecutar… veremos con qué orden se van generando los números.

Bien, intentemos eliminar las puestas a 0 de los elementos del buffer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

int fibonacci_buffer2(int n)
{
static int *fbuffer=NULL; /* Buffer */
static int bufsize=0; /* Tamaño de buffer */
static int bpos=0; /* Recorre buffers */
int n3; /* n-2 */

if (n>2)
{
n3=n-2;
if (fbuffer==NULL)
{
fbuffer = (int*) malloc((n3 * sizeof(int)));
bufsize=n3; /* Mantenemos bufsize por si redimensionamos el buffer */
}
else if (bufsize<n3)
{
fbuffer = (int*) realloc(fbuffer, n3 * sizeof(int));
bufsize=n3;
}

/* Utilizamos bpos para saber cuál es el último elemento del buffer */
/* que hemos rellenado. */
if (bpos>=n3) /* Si se encuentra el fibonacci del número que buscamos */
return fbuffer[n3-1]; /* en memoria, lo devolvemos directamente */
else
{
/* Si el fibonacci no se encuentra, vamos a generarlo */
fbuffer[n3-1] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2);
bpos=n3;
return fbuffer[n3-1];
}

/* return fibonacci_simple(n-1) + fibonacci_simple(n-2); */
}
else if (n==2) /* Ponemos esto para agilizar un poco el proceso */
return 1;
else if (n==1)
return 1;
else if (n==0)
return 0;
else if (n==-1) /* Un caso nuevo n==-1 */
free(fbuffer); /* Liberamos memoria */

return -1; /* Error */
}

Con este algoritmo, consigo generar la secuencia en 2ms. Bastante más rápido que con el primer algoritmo, parece que la puesta a 0 del buffer llevaba su tiempo.

Para concluir, quiero proponer otra solución basada en arrays, supongo que muchos estaréis más familiarizados con estos:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

int fibonacci_buffer3(int n)
{
static int fbuffer[MAX_FIB];
static int bufsize=0; /* Tamaño de buffer */
int n3; /* n-3 */

if (n>2)
{
n3=n-3;

if (bufsize>n3) /* Si se encuentra el fibonacci del número que buscaos */
return fbuffer[n3]; /* en memoria, lo devolvemos directamente */
else
{
/* Si el fibonacci no se encuentra, vamos a generarlo */
fbuffer[n3] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2); /* y lo guardamos */
bufsize=n3+1;
/* Al ser fibonacci recursivo, y asignar el tamaño después de la generación */
/* el buffer se rellenará por orden, es decir, el primero que se rellenará */
/* será el [0], luego el [1], luego el [2]... */
return fbuffer[n3];
}

}
else if (n==2) /* Ponemos esto para agilizar un poco el proceso */
return 1;
else if (n==1)
return 1;
else if (n==0)
return 0;

return -1; /* Error, seguramente me hayan pasado un n negativo*/
}

Esta solución es muy parecida a las anteriores, aunque nos quitamos del medio la reserva de memoria, reducimos las líneas de código, ya que no vamos a alojar tantos valores diferentes… para esta secuencia serían unos 48 * 4 (sizeof(int)) = 192 bytes, y bufsize la utilizamos para ver cuál es el último elemento del buffer con información válida (como vimos antes, se rellenarán por orden, así que sólo tendríamos que llevar la cuenta). Las variables estáticas, como dije, podemos hacerlas globales (y quitarles el static, aunque queda más elegante como static).

Con esta solución tardo unos 5ms de media en generar la secuencia de números.

Foto: Eustaquio Santimano (Flickr)

También podría interesarte....

There are 3 comments left Ir a comentario

Pingback: Bitacoras.com / 21 junio, 2010 at 9:31
Pingback: BlogESfera.com / 21 junio, 2010 at 20:30
Eggy Car / 28 noviembre, 2023 at 4:45
Usando Google Chrome 119.0.0.0 en Windows NT
Wow, great post. it gave me a lot of useful information. I look forward to your next posts.