Algoritmos recursivos


Una de las herramientas más potentes de la programación es la recursividad. Un algoritmo recursivo es aquel que se define en términos de sí mismo. Recordando la película Inception, cada nivel de sueño en que se encontraban los personajes encapsulaba a otro nivel de sueño, hasta que llegaban al nivel de sueño deseado para cumplir su objetivo. En términos recursivos sería algo así:

void CapaSuenno(int nivel)
{
	if(nivel == 3)
	{
		printf(“Llegamos al nivel deseado\n”);
		return;
	}
	else{
		printf("Estamos en en el nivel %d\n", nivel);
		CapaSuenno(nivel+1);
	}
}

Las llamadas recursivas se almacenan en una pila, por lo que en cada llamada recursiva se hace una copia de todas las variables locales. El algoritmo anterior se almacenaría así en la pila:

Pila del algoritmo recursivo

Fig1 Pila del algoritmo recursivo

Es muy importante a la hora de crear un algoritmo recursivo definir una parada. Supón que en el algoritmo anterior llámaramos recursivamente a CapaSuenno(nivel) en lugar de nivel-1, siempre se ejecutaría la llamada recursiva CapaSuenno(1), y obtendríamos un error de desbordamiento de la pila del sistema.

Ese momento de parada es lo que se conoce como caso base, en el algoritmo CapaSuenno el caso base es nivel==3. Entonces, cuando diseñemos un algoritmo recursivo tenemos que lograr que cada llamada recursiva resuelva un problema más pequeño que tienda a acercarse al caso base.

Cálculo de la sucesión de fibonacci:

int fib(int n)
{
	if(n==0 || n==1)
	  return 1;
	return fib(n-1) + fib(n-2);
}

Podemos ver que el algoritmo siempre trabaja para darle solución a problemas más pequeños (n-1) y (n-2), y su caso base sería cuando n sea cero o uno.

Este es el árbol que genera las llamadas recursivas, donde las hojas del árbol son los casos base:

Arbol de ejecución del algoritmo fibonacci

Fig2 Árbol de ejecución del algoritmo fibonacci

Conclusiones

Los algoritmos recursivos son una potente herramienta para resolver problemas debido a su elegancia y fácil implementación. Sus principales desventaja radica en que presentan menor eficiencia en cuanto a memoria y tiempo, y realizan cálculos redundantes, es decir, realizan varias llamadas de un mismo caso recurrente, como en el ejemplo del árbol generado por fibonacci.

Una técnica de programación que soluciona esta desventaja es la programación dinámica, la cual estaré tratando en próximos artículos. Por ahora es todo, cualquier duda puedes dejarla en los comentarios. Hasta la próxima.

  • JO

    Muy bueno, espero la de dinámica!