PDF de programación - Recursividad

Tema 2:

Recursividad

Estructura de datos y de

la Información

Facultad de Informática

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

La pila y los registros de activación

• Cada vez que se hace una llamada 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 y pará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 la
llamada 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 la ejecució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
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

2

Facultad de Informática
Facultad de Informática
Facultad de Informática
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);

Instrucción de

retorno R1

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

3

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

Factorial (3)

a

l
i

p



a

l


e
d



o
d
a
t
s
E

Registro de
activación

Resultado

n

Dir. retorno

?
3
R1

Memoria
(Pila Recursiva)

Primera
llamada

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

4

Factorial (3) = 3 * Factorial(2)

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

a

l
i

p



a

l


e
d



o
d
a
t
s
E

Resultado

n

Dir. retorno

?
2
R2
?
3
R1

Memoria

Segunda
llamada

Primera
llamada

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

5

Factorial (2) = 2 * Factorial(1)

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

a

l
i

p



a

l


e
d



o
d
a
t
s
E

Resultado

n

Dir. retorno

?
1
R2
?
2
R2
?
3
R1

Memoria

Tercera
llamada

Segunda
llamada

Primera
llamada

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

6

Factorial (1) = 1 * Factorial(0)

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

a

l
i

p



a

l


e
d



o
d
a
t
s
E

Resultado

n

Dir. retorno

1
0
R2
?
1
R2
?
2
R2
?
3
R1

Memoria

Cuarta
llamada

Tercera
llamada

Segunda
llamada

Primera
llamada

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

7

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

Retorno

a

l
i

p



a

l


e
d



o
d
a
t
s
E

Resultado

n

Dir. retorno

1
1
R2
?
2
R2
?
3
R1

Memoria

Tercera
llamada

Segunda
llamada

Primera
llamada

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

8

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

Retorno

a

l
i

p



a

l


e
d



o
d
a
t
s
E

Resultado

n

Dir. retorno

1
2
R2
?
3
R1

Memoria

Segunda
llamada

Primera
llamada

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

9

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

Retorno

a

l
i

p



a

l


e
d



o
d
a
t
s
E

Resultado

n

Dir. retorno

2
3
R1

Memoria

Primera
llamada

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

10

Facultad de Informática
Facultad de Informática
Facultad de Informática
Facultad de Informática

Fin

• Finalmente, acabaría la ejecución de la llamada Factorial(3) y retornaría a

la instrucción inicial R1

Resultado

n

Dir. retorno

2
3
R1

Memoria

Resultado := 6

© 2005

Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad
Tema 2: Recursividad

11