Vistas de página en total

viernes, 1 de noviembre de 2013

Recursividad

La recursión es un proceso muy natural en la programación ya que con la práctica es muy fácil implementarla, profundicemos un poco...

Caso contrario de la iteración, la recursión va de un caso general a un caso particular en donde se va desglosando en subproblemas hasta llegar a un caso en donde el problema es obvio y evidente.

Pongamos el famoso ejemplo del factorial de un número aplicado en programación con la Recursión.

Se tiene un número n! con n = 5, la solución a el factorial de este número no la conocemos, pero si profundizamos y buscamos la solución de raíz llegaremos al resultado.

Donde:

5! = 5 * (4!)

5! = 5 * 4 * (3!) 

5! = 5 * 4 * 3 * ... (1!)

así hasta llegar al caso en el cuál sea obvio, como el factorial de 1! = 1.  

En pseudocódigo la función recursiva como solución a este problema sería de la siguiente manera:


Fact(n){

 si n == 1

   ret 1;  

ret n * Fact(n-1); 

}

//(n==1) Nuestro caso obvio donde conocemos el resultado y también es nuestro punto donde la recursión pare y nos devuelva el resultado.

//(n*Fact(n-1)) Aquí n multiplicará al valor de n restandole 1 y así sucesivamente hasta llegar al caso cuando n valga 1 y nos arroje la multiplicación de n hasta 1.

Cabe decir que en C o C++ bien codificado el algoritmo funciona de maravilla, aunque, no para números muy grandes, por el stack de la pila recursiva de C. Pero existen maneras de hacerlo más óptimo con la memorización tema que veremos después en este blog.


No hay comentarios:

Publicar un comentario