sábado, 17 de abril de 2010

Algoritmos Recursivos

En ciencias de la computación, la recursividad es un elemento muy importante en la solución de algunos problemas. Por definición, un algoritmo recursivo es aquel que utiliza una parte de él mismo como solución al problema. La otra parte generalmente es la solución trivial, es decir, aquella cuya solución será siempre conocida, es muy fácil de calcular, o es parte de la definición del problema a resolver. Dicha solución sirve como referencia y además permite que el algoritmo tenga una cantidad finita de pasos.

La implementación de estos algoritmos se realiza generalmente en conjunto con una estructura de datos, la pila, en la cual se van almacenando los resultados parciales de cada recursión.


Ventajas:

-Algunos problemas son esencialmente recursivos, por lo cual su implementación se facilita mediante un algoritmo de naturaleza recursiva, sin tener que cambiarlo a un método iterativo, por ejemplo. -En algunas ocaciones el código de un algoritmo recursivo es muy pequeño

-Es un método natural de resolver problemas.

-Permite una gran potencia de cálculo.

-La corrección de los algoritmos se comprueba fácilmente.

Desventajas:

-Puede llegar a utilizar grandes cantidades de memoria en un instante, pues implementa una pila cuyo tamaño crece linealmente con el número de recursiones necesarias en el algoritmo. Si los datos en cada paso es muy grande, podemos requerir grandes cantidades de memoria.

Se recomienda aplicar una solución no recursiva cuando el número de cálculos que se repiten sea grande o exista una solución iterativa que sea sencilla de codificar.

Ejemplo Algoritmo Recursivo

__________________________________________________________________
FUNCIÓN Factorial(n)
VAR resultado: Entero

SI (n<2) ENTONCES
resultado = 1;
SINO
resultado = n * Factorial(n-1);
FSI

RETORNA resultado;
FUNCIÓN
__________________________________________________________________

Factores que influyen en el tiempo de un algoritmos

Recursos computacionales:

Diseño del algoritmo Complejidad del problema (p.ej. tamaño de las entradas) Hardware (arquitectura, MHz, MBs…) Calidad del código Calidad del compilador (optimizaciones)

Recursos no computacionales:
Complejidad del algoritmo Disponibilidad de bibliotecas reutilizables

Eficiencia
Tipos de análisis ¿Cómo medimos el tiempo de ejecución de un algoritmo? Mejor caso
En condiciones óptimas (no se usa por ser demasiado optimista).

Peor caso
En el peor escenario posible (nos permite acotar el tiempo de ejecución).

Caso promedio
Caso difícil de caracterizar en la práctica.


No hay comentarios:

Publicar un comentario