Recursividad

Tema 2: Recursividad
Estructura de datos y de la Información Facultad de Informática

Facultad de Informática

La pila y los registros de activación
• Cada vez que se hace una llamada a unarutina (procedimiento o función) se crea un registro de activación. • Un registro de activación es un trozo de memoria donde se guardan los valores de las constantes, variables y parámetros por valor dela rutina que se está ejecutando. • Además, si una rutina A tiene entre sus instrucciones una llamada a la rutina B, la ejecución de A se para en la instrucción donde se genera la llamada a B y seguarda, en su correspondiente registro de activación, la dirección de la instrucción de retorno junto a los datos que manejaba hasta ese momento. • En el momento en que finaliza la ejecución de unarutina, su registro de activación se destruye. • Finalmente, todos los registros de activación se almacenan en un segmento de la memoria del ordenador llamado Stack o Pila.

© 2005

Tema 2:Recursividad

2

Facultad de Informática

Recursividad: proceso de llamadas
• Supongamos que tenemos el siguiente código recursivo:
function Factorial (n: integer): integer; begin if n = 0 thenFactorial := 1 else Factorial := n * Factorial(n-1); end;

Instrucción de retorno R2

• Veamos a continuación cómo funcionaría la llamada
Resultado := Factorial (3);
Instrucción de retorno R1

© 2005Tema 2: Recursividad

3

Facultad de Informática

Factorial (3)
Estado de la pila

Resultado n Dir. retorno

? 3 R1

Primera llamada

Memoria
Registro de activación © 2005(Pila Recursiva)
Tema 2: Recursividad
4

Facultad de Informática

Factorial (3) = 3 * Factorial(2)
Estado de la pila

Resultado n Dir. retorno

? 2 R2 ? 3 R1

Segunda llamada Primera llamadaMemoria
© 2005

Tema 2: Recursividad

5

Facultad de Informática

Factorial (2) = 2 * Factorial(1)
Estado de la pila

Resultado n Dir. retorno

? 1 R2 ? 2 R2 ? 3 R1

Tercera...