PDF de programación - Programación I Recursividad

Imágen de pdf Programación I Recursividad

Programación I Recursividadgráfica de visualizaciones

Publicado el 27 de Diciembre del 2019
575 visualizaciones desde el 27 de Diciembre del 2019
615,8 KB
21 paginas
Creado hace 3a (06/09/2017)
Programación I
Recursividad

http://proguno.unsl.edu.ar
[email protected]

Recursividad

 Técnica de resolución de problemas

particulares.

 La definición de un concepto es recursiva si

el concepto es definido en términos de sí
mismo.

 Ejemplos:

 Definición de la función factorial.
 Definición de los números naturales.
 …

2

3

Definiciones recursivas

 En una definición recursiva, en general,

distinguimos dos partes:

 Uno o más casos base o elementales.

 Definición recursiva o caso general.

4

Recursividad en Computación

 Se encuentra presente en:

 Definiciones recursivas de módulos.
 Definiciones recursivas de datos.

 La mayor parte de los lenguajes de

programación soportan la recursividad.

 Es otra técnica para realizar repeticiones.
Aunque no siempre sea la mas adecuada.

5

Definiciones recursivas de módulos

 Un módulo (función en C) es recursivo cuando:

1. En su cuerpo existe al menos una invocación a sí

mismo (caso recursivo o general).

2. Existe uno o varios casos de menor tamaño que

pueden resolverse directamente sin necesidad
de recursión (caso(s) base(s)).

6

Ejemplo I: Factorial

Definición
matemática de la
función factorial

!: ℕ0 →ℕ

n × (n-1)!, n > 0

n! =

Definición de la
función factorial
en C

long factorial(int n){

if (n == 0)
return 1;

1, n = 0

else

return n * factorial(n-1);

}

7

Ejemplo I: Factorial

printf("%ld \n", factorial(2));

factorial(2)

2 * factorial(1)

1 * factorial(0)

1

8

Ejemplo II: Sucesión de Fibonacci

término f0 f1 f2 f3 f4 f5 f6 f7 f8

f9 f10 f11 ...
valor 0 1 1 2 3 5 8 13 21 34 55 89 ...



 f0 = 0
 f1 = 1
 fn = fn–1 + fn–2

caso base
caso base
caso general

9

Ejemplo II: Sucesión de Fibonacci

fibonacci(4)



fibonacci(3) + fibonacci(2)



fibonacci(2) + fibonacci(1) fibonacci(1) + fibonacci(0)



fibonacci(1) + fibonacci(0) 1



1



0



1



0

10

Tipos de Recursividad

 Lineal vs. Múltiple

 Lineal: existe una única invocación recursiva.
 Múltiple: existe más de una invocación recursiva.

 Anidada: dentro de una invocación recursiva ocurre como

parámetro otra invocación recursiva.

int ackerman(int n, int m){

if (n == 0) return m + 1;
else if(m == 0) return ackerman(n - 1, 1);
return ackerman(n - 1, ackerman(n, m - 1));

}

11

Tipos de Recursividad

 Directa vs. Indirecta.

 Directa: el módulo recursivo se llama a sí mismo.
 Indirecta: se tienen varios módulos que se llaman unos a

otros formando un ciclo.
 función A → función B → función A …
 función A → función B → función C → función D → función A …
 Ejemplo: funciones par e impar:

 n es par si n − 1 es impar,
 n es impar si n − 1 es par,
 0 es par

12

Stack de Ejecución

 Mantiene la información del estado de

ejecución de cada módulo invocado en un
programa.

 Guarda los registros de activación de los

módulos invocados.

13

Stack de Ejecución

Tope del
Stack de
Ejecución

Variables locales

de función Y
Dirección de

retorno

Parámetros de Y

Variables locales

de función X
Dirección de

retorno

Registro de
activación
para función Y

Registro de
activación para
función X

Parámetros de X

. . .

.

.

.

14

Registros de Activación

 Un registro de activación de un módulo

almacena el Ambiente (variables locales,
dirección de retorno, etc.) de un módulo.

 En el tope del stack de ejecución se

encuentra el registro de activación del
módulo que se está ejecutando.

 Por debajo, los registros de activación de

aquellos cuya ejecución aún está pendiente
de finalizar.

15

EJEMPLO

1. int funcion1(int a){
2. int b;
3. b = funcion2(a+6);
4. return a + b;
5. }
6. int funcion2 (int c){
7. return c - 3;
8. }
9. int main() {
10. int b = 3;
11. printf(“%d”,b + funcion1(43));
12. printf(“Fin");
13. }

16

Profundidad de la Recursión

 Número máximo de registros de

activación en el stack de ejecución
para una entrada de datos dada.

17

Casos particulares

 Inicialización

 Condición dentro de módulo 
 Usar variables globales 
 Módulos anidados (si lo permite el

lenguaje) 

 Antes de la invocación 

18

Casos particulares

 Actualización de valores entre
llamadas (p.e. imprimir datos y
posiciones)
 Usar variables globales 
 Usar parámetros extras para pasar

valores 

19

Ventajas e Inconvenientes de la
Recursividad
 Permite definir un conjunto potencialmente

infinito de objetos por medio de una
expresión finita. 

 Los algoritmos o soluciones recursivas son

útiles, particularmente, cuando existe una
definición recursiva. 
 Solución compacta.
 Adaptadas en forma directa a la definición del

problema.

20

Ventajas e Inconvenientes de la
Recursividad
 Consumo de tiempo y espacio (creación y
destrucción de registros de activación en el
stack de ejecución). 

 No contribuye a hacer equivalentes las

estructuras estática y dinámica del programa .
 Dificulta la depuración del código.
 Oculta las iteraciones.

21
  • Links de descarga
http://lwp-l.com/pdf17089

Comentarios de: Programación I 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