Recursividad Estructura De Datos

Recursividad
T T E E M M A A 1 1
Elementos de Programación I

CONTENIDO DEL TEMA
1.- Introducción. 2.-Asignación estática y dinámica de memoria. 3.-Verificación de funciones y procedimientos recursivos. 4.-Escritura de programas recursivos.

TEMA 2
Recursividad

Introducción
• Definición de Recursividad: Técnica de programación muy potente que puede ser usada en lugar de la iteración.• Ambito de Aplicación:
– General. – Problemas cuya solución se puede hallar solucionando el mismo problema pero con un caso de menor tamaño.

Introducción
• ¿En qué consiste la recursividad?
– En el cuerpo de sentencias del se invoca al propio “una versión más pequeña” del problema original.

• Aspecto de un subalgoritmo recursivo.
Algoritmo Recursivo(...); Inicio ... Recursivo(...); ...Fin. Elementos de Programación I

•
– Problemas “casi” irresolubles con las estructuras iterativas. – Soluciones elegantes. – Soluciones más simples.

• Condición necesaria: ASIGNACIÓN DINÁMICA DE MEMORIA
Elementos de Programación I

Introducción
• Ejemplo: Factorial de un natural. 1 si n=0 Factorial(n)= n*Factorial(n-1) si n>0 FUNC Factorial(n:NATURAL):NATURAL Inicio SI n=0 ENTONCESRESULTADO←1 ← ENOTROCASO RESULTADO←n*Factorial(n-1) FINSI Fin
Elementos de Programación I

Introducción
24
F(4)=4 * F(3)

6 2 1

F(3)=3 * F(2)

F(2)=2 * F(1)

F(1)=1 * F(0)

Elementos de Programación I

Introducción
Registro de Activación. Dirección de Retorno. Pila (Stack). Vinculación.

Asignación estática y dinámica de memoria
• Partimos del siguiente ejemplo PROC uno (↓x,↓y:REAL) Variables z:NATURAL Inicio ... ... Fin.

Elementos de Programación I

Elementos de Programación I

Asignación estática y dinámica de memoria
• Asignación estática
• Se reserva espacio en memoria a partir de una posición FIJA, tanto para el código como para los parámetros formales y variables locales de cada subprograma. • x y z • La zona reservada para variables locales y parámetrosformales usualmente preceden al código del subprograma
Elementos de Programación I
Direcciones altas

Asignación estática y dinámica de memoria
Código Vbles Locales ........ Primer Parámetro Dirección Vuelta Código Vbles Locales ........ Segundo Parámetro Primer Parámetro Dirección Vuelta Código Vbles Globales ........ Subprograma 1 Subprograma 2

programa principal

Memoria

Elementos deProgramación I

Asignación estática y dinámica de memoria
•PROBLEMA Vinculación de variables en tiempo de compilación

Asignación estática y dinámica de memoria
• Asignación dinámica
• Asignación de cada variable, parámetro x→ 1 y→ 2 z→ 3 • Dirección de retorno→0 •

¿almacenamiento de las distintas llamadas recursivas?

Pérdida de los valores de las variables

Elementos de ProgramaciónI

Elementos de Programación I

Asignación estática y dinámica de memoria
Tiempo de ejecución:Se reserva espacio para las variables y ejecución:Se parámetros a partir de la situación actual de CAB
34 33 32 31 30 29 28 27 Memoria Cab Situacion 1

Asignación estática y dinámica de memoria
• Llamada al subalgoritmo

34 33 32 31 30 29 28 27 Memoria Z Y X Direccion vuelta Cab Situacion 2Elementos de Programación I

Elementos de Programación I

Asignación estática y dinámica de memoria
• Llamada recursiva al algoritmo
36 35 Segunda Llamada 34 33 32 Primera Llamada 31 30 29 28 Z Y X Direccion vuelta Z Y X Direccion vuelta Memoria Cab

Asignación estática y dinámica de memoria
• Ejemplo con la función factorial Algoritmo Factorial(↓ n:NATURAL):NATURAL Inicio SI n=0ENTONCES RESULTADO←1 ← ENOTROCASO RESULTADO ← n*Factorial(n-1) FINSI Fin R2 La invocación inicial es: Resultado ← Factorial(3)

Stack
Elementos de Programación I

R1
Elementos de Programación I

Asignación estática y dinámica de memoria
Cab Cuarta Llamada Tercera Llamada Segunda Llamada n Dir. Vuelta Resultado n Dir. Vuelta Resultado n Dir. Vuelta Resultado n Dir. Vuelta 0 R2 ? 1 R2 ? 2...