Algoritmos Recursivos

Un Algoritmo Recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

FUNCION Factorial (n)

VAR resultado: Entero

SI (n<2)>

resultado =1;

SINO

resultado = n * Factorial(n-1);

FSI

RETORNA resultado;
FFUNCION

Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N de esta forma al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.

Ventajas:

1. Resolucion de problemas complejos

2. Eficiencia del algoritmo

3. Paralelismo

4. Acceso a memoria

5. Control de redondeo

Desventajas:

La principal desventaja de este método es su lentitud en la repetición del proceso recursivo: los gastos indirectos de las llamadas recursivas a la resolución de los subproblemas, junto con el hecho de tener que almacenar la pila de llamadas puede empeorar cualquier mejoras hasta entonces lograda. Esta tarea sin embargo, depende del estilo de la implementación: con casos base lo suficientemente grandes, se reducen los gastos indirectos de la repetición de la llamada.

Otra desventaja o inconveniente importante, es la dificultad o incluso inconveniencia de aplicar el método a situaciones en las que la solución al problema general no se deriva de la suma directa y simple de los subproblemas(partes). Esto se presenta por ejemplo cuando son relevanters las interacciones o efectos mutuos entre los subproblemas, lo que genera nuevos subproblemas, al considerar cada una de estas interacciones, incrementando exponencialmente el número de subproblemas a considerar, al incrementarse la complejidad de la situación general y de sus componentes.

De modo similar, el algoritmo puede no ser aplicable cuando las interacciones no son predecibles de preciso.