next up previous contents
Siguiente: Peligros en la recursividad Subir: Recursión Anterior: Recursión   Índice General

La serie Fibonacci

Una de las series más famosas es sin duda alguna la serie de Fibonacci:

$\displaystyle 1,1,2,3,5,8,13,21,34,\dots
$

Un poco de observación es sufucuente para encontrar que cualquier número (a partir del tercero de la serie, osea el segundo 1) es igual a la suma de los dos números anteriores.

Daremos en primer lugar la versión iterativa. En este algoritmo deseamos encontrar el $ n$ -ésimo número de la serie Fibonacci. Así si $ n=4$ el resultado del algoritmo debe ser $ 3$ ; si $ n=6$ el resultado debe ser $ 8$ . La versión iterativa empieza desde los primeros 1's, sumándolos y encontrando el tercero, luego para encontrar el cuarto número se suman el tercero (recién encontrado) y el segundo, y así en adelante hasta encontrar el número buscado.

#include <iostream>

int main (int argc, char * const argv[]) {
int i,n,fib,fib1,fib2,fibx;
	
std::cout<<"Un numero entero:";
std::cin>>n;
fib1=2; fib2=1; i=3;
if((n==1)||(n==2)) 
	fib=1;
else{
	do{
		fib = fib1 + fib2;
		fibx = fib1; i++;
		fib1 = fib;  fib2 = fibx;
	}while(i<n);
}	
std::cout << "\nEl "<<n<<"-esimo numero de 
             la serie Fibonacci es: "<<fib;
return 0;
}

La definición recursiva para encontrar todos los $ n$ primeros números de la serie Fibonacci es:

$\displaystyle \texttt{fib}(n)=\left\{\begin{array}{ll}
1 & \textrm{Si $n=1$ \'o...
...
\texttt{fib}(n-1)+\texttt{fib}(n-2) & \textrm{Si $n>2$}\\
\end{array}\right.
$

En el siguiente código, la solución que propone la recursividad resulta en una programación elegante, aunque costosa. El código que hace esto es:

( 1) #include <iostream>
( 2) //====================
( 3) int fib(int val){
( 4) 	if ((val==1)||(val==2))
( 5) 		return 1;
( 6) 	else
( 7) 		return (fib(val-1)+fib(val-2));
( 8) }
( 9) //====================
(10) int main (int argc, char * const argv[]) {
(11) 	int n;
(12) 	std::cout<<"Numero entero:";   std::cin>>n;
(13) std::cout<<"\nEl "<< n 
(14)          <<"-esimo numero fibonacci es: "<< fib(n);
(15) return 0;
(16) }

Como regla general, cualquier algoritmo recursivo se puede reescribir en un algoritmo iterativo. La ventaja de tener un algoritmo iterativo es que no se usa una pila para guardar llamadas a la misma función de manera recursiva, esto es una ventaja porque el espacio de memoria destinado al uso de la pila es generalmente limitado, de manera que cuando se hacen demasiadas funciones push seguramente llegará el momento en que la pila ``se desborde'', que por cierto es un término usado en computación para decir que ya no hay más espacio disponible en la pila.


next up previous contents
Siguiente: Peligros en la recursividad Subir: Recursión Anterior: Recursión   Índice General
Abdiel Caceres-Gonzalez Jun-02-2005