Funcionamiento interno de la recursividad

Funcionamiento interno de la recursividad

Cuando se llama a una función recursiva, se crea un nuevo juego de variables locales, de este modo, si la función hace una llamada a si misma, se guardan sus variables y parámetros en una pila de datos, y la nueva instancia de la función trabajará con su propia copia de las variables locales, cuando esta segunda instancia de la función retorna, recupera las variables y los parámetros de la pila y continua la ejecución en el punto en que había sido llamada. La mayoría de los lenguajes de alto nivel como C, C++ o Java permiten la construcción de subrutinas, funciones que pueden ser llamadas a si mismas (recursivas) de manera natural.

A continuación se muestra una función recursiva que calcula la factorial de un número n:

int factorial( int n )

{

if ( n == 0 )

return 1;

else

return n * factorial( n-- );

}

Veamos paso a paso que es lo que ocurre cuando realizamos una llamada a dicha función con un valor de n igual a 3, factorial (3):

llamada 1 n = 3 n != 0 n * factorial(2)

llamada 2 n = 2 n != 0 n * factorial(1)

llamada 3 n = 1 n != 0 n * factorial(0)

llamada 4 n = 0 n == 0 return 1 1(regresa a 3´)

llamada 3´ n = 1 return n * 1 1 (regresa a 2´)

llamada 2´ n = 2 return n * 1 2 (regresa a 1´)

llamada 1´ n = 3 return n * 2 6 (termina)

Podemos observar que en cada llamada de función el valor de n es conservado en cada llamada a función, en realidad el valor de n es colocado en una pila y posteriormente es recuperado cada vez que regresa a la llamada de cada función factorial.

Torres de Hanoi

El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:

...