PDF de programación - Recursividad

Imágen de pdf Recursividad

Recursividadgráfica de visualizaciones

Publicado el 11 de Julio del 2017
494 visualizaciones desde el 11 de Julio del 2017
241,4 KB
11 paginas
Creado hace 16a (22/03/2005)
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
  • Links de descarga
http://lwp-l.com/pdf5305

Comentarios de: Recursividad (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad