4.3 Mecanica Recursion.

La mecánica de la recursividad está basada en una “pila”. Cuando un módulo recursivo se está ejecutando se crea en la memoria de la computadora una pila donde se almacenan los valores de los parámetros y de las variables locales del módulo. Si el módulo es función también se guarda en la pila el valor que adquiere la misma.
Para cada llamada del módulo se almacenan en la pila los nuevos valores de los parámetros y de las variables locales, creándose un nuevo “registro de activación”. De tal forma que, la pila de recursión está formada por registros de activación. Al terminar una llamada al módulo, es decir, cuando se cumple la definición base, se libera (sale) el registro de activación que se encuentra en el tope de la pila. De esta forma es como puede “recordar” qué valores tenían los parámetros y las variables locales en la llamada anterior.
Si observamos el proceso que seguimos para calcular 4! vemos que el valor de n fue cambiando conforme fuimos entrando en recursión y que al salir de recursión necesitábamos recordar el valor que tenía n en la expresión anterior. Esto quiere decir que los valores que fue adquiriendo n fueron entrando a la pila.
No sólo debe recordar los valores que tenían los parámetros y las variables locales al realizarse la correspondiente llamada al módulo sino que también tiene que recordar qué instrucción debe realizar al terminar esa llamada. De tal forma que los registros de activación están compuestos básicamente de:

1. Instrucción a la que debe regresar el control una vez terminada la ejecución actual del módulo.
2. Todos los parámetros y variables locales del módulo.
3. Si el módulo recursivo es una función el valor que adquiere la misma, ya que éste se debe regresar.
Para hacer la representación de la pila de recursión numeramos las instrucciones a las que debe regresar el control una vez terminada la ejecución del módulo recursivo y estos valores son los que ponemos en la pila. 

Examinaremos que significa lo anterior cuando se aplica la función factorial. 4! Es un caso mas complejo que 3!. La transformación que se aplica al numero a para obtener 3 es sencillamente restar 1. Si restamos 1 de 4 de manera sucesiva llegamos a 0, que es el caso trivial. Así, si se puede definir 4! en términos de 3! y, en general, n! en términos de (n – 1)!, se podrá calcular 4! mediante la definición de n! en términos de (n – 1)! al trabajar, primero hasta llegar a 0! y luego al regresar a 4!. En el caso de la función factorial se tiene una definición de ese tipo, dado que:

n! = n * (n – 1)! Asi, 4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 * 0! = 4 * 3 * 2] * ] = 24

Estos son los ingredientes esenciales de una rutina recursiva: poder definir un caso “complejo” en términos de uno más “simple” y tener un caso “trivial” (no recursivo) que pueda resolverse de manera directa. Al hacerlo, puede desarrollarse una solución si se supone que se ha resuelto el caso más simple. La versión C de la función factorial supone que esta definido (n –1)! y usa esa cantidad al calcular n!.

Otra forma de aplicar estas ideas a otros ejemplos antes explicados. En la definición de a * b, es trivial el caso de b = 1, pues a * b es igual a a. En general, a + b puede definirse en términos de a * (b – 1) mediante la definición a * b = a * (b – 1) + a. De nuevo, el caso complejo se transforma en un caso mas simple al restar 1, lo que lleva, al final, al caso trivial de b = 1. Aquí la recursión se basa únicamente en el segundo parámetro, b.

Con respecto al ejemplo de la función de Fibonacci, se definieron dos casos triviales: fib(0) = 0 y fib(1) = 1. Un caso complejo fib(n) se reduce entonces a dos más simples: fib(n –1) y fib(n –2). Esto se debe a la definición de fib(n) como fib(n –1) + fib(n – 2), donde se requiere de dos casos triviales definidos de manera directa. Fib(1) no puede definirse como fib(0) + fib(−1) porque la función de Fibonacci no está definida para números negativos.

• Los parámetros y variables locales toman nuevos valores en cada llamada (no se trabaja con los anteriores).

 • Cada vez que se llama un método, el valor de los parámetros y variables locales se almacenan en la pila de ejecución. Cuando termina la ejecución se recuperan los valores de la activación anterior.

• El espacio necesario para almacenar los valores en memoria (pila) crece en función de las llamadas.

• Con cada llamada recursiva se crea una copia de todas las variables y constantes que estén vigentes, y se guarda esa copia en la pila.

 • Además se guarda una referencia a la siguiente instrucción a ejecutar.

• Al regresar se toma la imagen guardada (registro de activación) en el tope de la pila y se continúa operando. Esta acción se repite hasta que la pila quede vacía.