Algoritmia - Recursividad

Hola:

Quisiera que me respondan el siguiente post, mas que todo para reafirmar si lo que estoy pensando esta bien. Bueno, ya todos seguro conocen a la famosa funcion factorial recursiva. Ahora quisiera saber que sucede en la memoria con esto.

Por ejemplo si tengo la funcion factorial como sigue:

factorial(numero)
si numero=1 entonces
retornar 1
sino
retornar numero*factorial(numero-1)
fin si
fin factorial

Si hago factorial(5), bueno la respuesta es 120; pero ¿como se van almacenando las llamadas a las funciones?

Sé que es algo de una memoria pila. Sin embargo, como funciona esta memoria exactamente?, ¿es solo para las funciones recursivas?.

Segun lo que entendí yo, si hago factorial(5).

1° apilará factorial(5)
2° apilará factorial(4)
3° apilará factorial(3)
4° apilará factorial(2)
5° apilará factorial(1)

Aquí, como factoria(1) es el caso base, entonces comenzará a desapilar(liberar memoria)
(¿desapalir=liberar memoria?)

6° desapilará factorial(1)=1
7° desapilará factorial(2)=2
8° desapilará factorial(3)=6
9° desapilará factorial(4)=24
10° desapilará factorial(5)=120

La idea que tengo es correcta? o en algo me equivocado?. Ademas si fueran tan amables, me gustaria saber que sucede cada vez que declaramos una variable o una funcion o una constante; es decir, ¿en donde se guardan exactamente?

Gracias por su respuesta.

La idea no es correcta. En realidad, depende del lenguaje o microprocesador que estés usando, pero en cualquier caso la cosa no va por ahí.

Cada vez que llamas a una función, como factorial(), el programa salta al código de esa función, y mete en una pila la dirección desde donde has llamado, para volver una vez que factorial() haya terminado de trabajar. Esa pila se conoce como "pila de retornos".

Por poner un ejemplo, digamos que estoy leyendo las instrucciones de mi reproductor de DVD, en el capítulo de grabación. En una página dada, digamos que es la página 32, me dicen que antes de grabar tengo que formatear el disco, proceso que está descrito en la página 12. Lo que hago es poner un marcador en la página 32, entonces salto a la página 12, formateo, y luego retorno a la página 32 para seguir con la grabación.

Ahora imagina que en la página 12, sobre formatos, me dicen que tengo que ir a la página 7 porque, para formatear, antes tengo que decidir el tipo de formato, y esa información está allí. Tendré entonces que poner otra marca en la página 12, y saltar a la 7.

Como puedes ver, según se va cediendo el control a una nueva tarea, debo ir apilando las direcciones de retorno (desde la página 7, volver a página 12, luego volver a página 32). En el caso de un microprocesador, a menudo es necesario además meter en la pila información de contexto (ciertos registros o variables que se corromperían al cambiar de subrutina). Para colmo, cuando llamo a una función, ésta suele necesitar parámetros para ejecutarse, y esos también pueden a una pila, para poder acceder a ellos fácilmente (en ocasiones, si son pocos, van en registros).

Opcionalmente, ciertos lenguajes, como FORTH, tienen una "pila de retornos", en la que se van almacenando y consumiendo los valores que devuelven las llamadas a funciones.

Pero nada de esto es necesario para entender la idea de recursividad, que por tu post deduzco que no tienes clara. Para entender la recursividad, lo que debes comprender es el proceso de reducción de una expresión, que es muy parecido a una simplificación en matemáticas. La función factorial la puedes definir como sigue:

factorial(x) -> SI x = 1 ENTONCES 1 SINO x * factorial(x-1)

esto significa que el computador, donde vea "factorial", puede sustituir esa función por la expresión de la derecha, puesto que son equivalentes.

Por tanto, supón que me dan la expresión factorial(5). Para reducirla, voy por pasos:

Paso 1: factorial(5) -> 5 * factorial(4), puesto que 5 es distinto de 1.
Paso 2: 5*factorial(4) -> 5 * 4 * factorial(3), puesto que 4 es distinto de 1.
Paso 3: 5*4*factorial(3) -> 5 * 4 * 3 * factorial(2), puesto que 3 no es 1.
Paso 4: 5*4*3*factorial(2) -> 5*4*3*2*factorial(1), puesto que 2 no es 1.
Paso 5: 5*4*3*2*factorial(1) -> 5*4*3*2*1, puesto que ahora sí que tengo 1.
Paso 6: 5*4*3*2*1 -> 120, haciendo la multiplicación de enteros.

Esto, el microprocesador lo hace internamente con pilas, o con otros procedimientos alternativos (ciertos lenguajes, como Haskell o Clean, son naturalmente recursivos y usan un procedimiento llamado reducción de grafos). Eso no nos importa: lo que interesa es saber cómo funciona la recursividad.

Espero que esto te ayude un tanto a aclarar la situación.