Programer

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

Facultad
Facultad de Informática

La pila y los registros de activación
• Cada vez que se hace unallamada a una rutina (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 yparámetros por valor de la 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 lallamada a B y se guarda, 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 laejecución de una rutina, 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
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
then
Factorial := 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);

© 2005

Tema 2: Recursividad

Instrucción de
retorno R1

3

Facultad
Facultad de Informática

Estado de la pila

Factorial (3)

Resultado
n
Dir. retorno

?
3
R1Primera
llamada

Memoria
Registro de
activación
© 2005

(Pila Recursiva)
Tema 2: Recursividad

4

Facultad
Facultad de Informática

Estado de la pila

Factorial (3) = 3 * Factorial(2)Resultado
n
Dir. retorno

?
2
R2
?
3
R1

Segunda
llamada
Primera
llamada

Memoria
© 2005

Tema 2: Recursividad

5

Facultad
Facultad de Informática

Estado de la pila...