next up previous contents
Siguiente: La serie Fibonacci Subir: Apuntes para el curso Anterior: Ejercicio de programación   Índice General


Recursión

Un tema fundamental para los próximos temas es el de recusrión. La recursión es muy importante tanto en mateáticas como em computación, pues se usa recursión para definir procedimientos autosimilares.

Definición 6   Decimos que un objeto es recursivo si en su definición se nombra a sí mismo.

En programación, una función es recursiva si en el ámbito de esa función hay una llamada a sí misma, C/C++ permite esta clase de acciones. Los algoritmos recursivos dan elegancia a las soluciones de los problemas. Un ejemplo clásico es el factorial de un número.

Una manera de definir el factorial de un número $ n>1$ es:

$\displaystyle !n=\prod_{i=1}^{n}i,
$

es decir, el producto de todos los números enteros menores o guales que él, lo que se puede resolver fácilmente con una función iterativa, esto es, una función con un ciclo que itere suficientes veces, incrementando un valor y entonces ir almacenando en una variable el resultado de esas multiplicaciones.

Una implementación de esta definición iterativa es:

(1) int i,n;
(2) long double valorAc;	
(4) valorAc=1.0;
(5) std::cout << "Numero entero:";
(6) std::cin>> n;
(7) for(i=1; i<=n; i++)  valorAc = valorAc*i;
(8) std::cout<<"El factorial de "<<n<<" es:"<<valorAc;

El ciclo principal es en la línea (7). No hay ningún truco hasta aquí. La única observación importante es en la línea (2) en donde se declara el tipo long double para el valor del resultado, la razón para tal acción es que el número factorial crece muy rápido y aún con entradas en el rango de los caracteres (hasta 255), el factorial es muy grande. Este procedimiento computacional no hace uso de técnicas especiales empleadas para tratar números grandes.

Sin embargo una solución más elegante es usar la definición recursiva, y esta es:

$\displaystyle !n= n\,\ast\,!(n-1)
$

El programa en C/C++ es el que se muestra a continuación:

( 1) double factorial(double a){
( 2) 	if (a<=1) return 1.0;
( 3) 	  else    return (a *factorial(a-1.0));  }
( 4) 
( 5) int main (int argc, char * const argv[]) {
( 6) 	double n;
( 7)     std::cout << "Numero entero:";
( 8) 	std::cin>> n;
( 9) 	std::cout<<"El factorial de "<<n<<" es: "<< factorial(n);
(10)     return 0; }

Aquí hay varias cosas que señalar, en primer lugar se ha creado una nueva función, a diferencia de la definición iterativa en donde era suficiente trabajar en el programa principal. Esta función se llama factorial (como era de suponerse), y empieza su encabezado en la línea (1).

Allí mismo en la misma línea (1), es de notar que hemos emplado ahora el tipo double tanto para el tipo devuelto como para el tipo del argumento, a diferencia de la versión iterativa en donde empleábamos tipos diferentes. La razón es que al iniciar la recursión el argumento es del tipo devuelto, asi que deben ser del mismo tipo.

Cada llamada recursiva genera una entrada a una pila, en donde se guardan (como elementos) los estados generales del sistema al momento de hacer la llamada, entonces, cuando se termina la función se recupera una entrada de la pila. En la figura 16 ilustra cómo funciona la recursividad cuando se intenta obtener el factorial(5).

Figura 16: Recursividad cuando se ejecuta factorial(5)
Image recursiv



Subsecciones
next up previous contents
Siguiente: La serie Fibonacci Subir: Apuntes para el curso Anterior: Ejercicio de programación   Índice General
Abdiel Caceres-Gonzalez Jun-02-2005