Programer
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...
Regístrate para leer el documento completo.