![Page 1: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/1.jpg)
Recurrencia
Programación II
27-28 de enero de 2009
![Page 2: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/2.jpg)
Recurrencia
• Un concepto es recursivo si está definido a partir de su mismo
• Cada definición recursiva tiene un caso base y un caso recursivo
• Una función recursiva llama a su misma con otros valores de entrada
• Mayor dificultad: encontrar la definición recursiva
![Page 3: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/3.jpg)
Ejemplo: Factorial
funcion Factorial(n:natural) devuelve natural
si (n=0) entonces
devuelve 1; caso base
sino
devuelve n*Factorial(n-1);
fsi
ffuncion caso recursivo
![Page 4: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/4.jpg)
Ejecución
• ¿Qué pasa cuando ejecutamos una función recursiva?– relacionado con la ejecución de programas en
general– ayuda en la interpretación de funciones
recursivas
• Vamos a estudiar un modelo simplificado de la máquina
![Page 5: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/5.jpg)
La pila
• La máquina mantiene una pila para controlar la ejecución
• Cada elemento en la pila es un registro de activación
• Cuando el código entra en un bloque, se añade un elemento
• Cuando sale, se remueve
Registro 4
Registro 3
Registro 2
Registro 1
![Page 6: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/6.jpg)
Registro de activación
• Cada registro de activación contiene los siguientes componentes:– Parámetros– Variables locales/resultados intermedios– Resultado final
• Cada componente puede ser de valor o de referencia
![Page 7: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/7.jpg)
Referencia
• Un parámetro, una variable o el resultado de una función puede ser de referencia – Ejemplo: puntero en C
• Una referencia no contiene el valor mismo
• En cambio, contiene la dirección a la ubicación en memoria donde halla el valor
int c=5;
int *d=&c;c 5
d
![Page 8: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/8.jpg)
Ejemplo: Factorial
• Suponemos que queremos saber cuál es el resultado de Factorial(3)
• Usamos el modelo de la pila para analizar la llamada Factorial(3)
• Introducimos los registros de activación correspondientes
![Page 9: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/9.jpg)
Ejemplo: Factorial
Factorial(3)
![Page 10: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/10.jpg)
Ejemplo: Factorial
Factorial(3)
n 3
Factorial(n-1)
Resultado
![Page 11: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/11.jpg)
Ejemplo: Factorial
Factorial(3)
n 3
Factorial(n-1)
Resultado
n 2
Factorial(n-1)
Resultado
![Page 12: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/12.jpg)
Ejemplo: Factorial
n 1
Factorial(n-1)
Resultado
Factorial(3)
n 3
Factorial(n-1)
Resultado
n 2
Factorial(n-1)
Resultado
![Page 13: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/13.jpg)
Ejemplo: Factorial
n 1
Factorial(n-1)
Resultado
n 2
Factorial(n-1)
Resultado
Factorial(3)
n 3
Factorial(n-1)
Resultado
n 0
Factorial(n-1)
Resultado
![Page 14: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/14.jpg)
Ejemplo: Factorial
n 1
Factorial(n-1) 1
Resultado
n 2
Factorial(n-1)
Resultado
Factorial(3)
n 3
Factorial(n-1)
Resultado
n 0
Factorial(n-1)
Resultado
![Page 15: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/15.jpg)
Ejemplo: Factorial
n 1
Factorial(n-1) 1
Resultado
Factorial(3)
n 3
Factorial(n-1)
Resultado
n 2
Factorial(n-1) 1
Resultado
![Page 16: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/16.jpg)
Ejemplo: Factorial
Factorial(3)
n 3
Factorial(n-1) 2
Resultado
n 2
Factorial(n-1) 1
Resultado
![Page 17: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/17.jpg)
Ejemplo: Factorial
Factorial(3) 6
n 3
Factorial(n-1) 2
Resultado
![Page 18: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/18.jpg)
Ejemplo: Factorial
Factorial(3) 6
![Page 19: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/19.jpg)
Ejercicio 1.5
• Escribir una función recursiva EsPrimo que devuelve si o no un número natural n es primo
• Usar la pila para interpretar el resultado de EsPrimo(5)
![Page 20: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/20.jpg)
Ejercicio 1.5
funcion EsPrimo(n:natural) devuelve booleano
devuelve Primo(n,2);
ffuncion
![Page 21: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/21.jpg)
Ejercicio 1.5
funcion Primo(n,k:natural) devuelve booleano
si (k >= n) entonces
devuelve cierto;
sino si (n mod k = 0) entonces
devuelve falso;
sino
devuelve Primo(n,k+1);
fsi
ffuncion
![Page 22: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/22.jpg)
Ejercicio 1.5
EsPrimo(5)
![Page 23: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/23.jpg)
Ejercicio 1.5
EsPrimo(5)
n 5
Primo(n,2)
Resultado
![Page 24: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/24.jpg)
Ejercicio 1.5
EsPrimo(5)
n 5
Primo(n,2)
Resultado
n 5
k 2
Primo(n,k+1)
Resultado
![Page 25: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/25.jpg)
Ejercicio 1.5
n 5
k 2
Primo(n,k+1)
Resultado
EsPrimo(5)
n 5
Primo(n,2)
Resultado
n 5
k 3
Primo(n,k+1)
Resultado
![Page 26: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/26.jpg)
Ejercicio 1.5
n 5
k 3
Primo(n,k+1)
Resultado
n 5
k 2
Primo(n,k+1)
Resultado
EsPrimo(5)
n 5
Primo(n,2)
Resultado
n 5
k 4
Primo(n,k+1)
Resultado
![Page 27: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/27.jpg)
Ejercicio 1.5
n 5
k 4
Primo(n,k+1)
Resultado
n 5
k 5
Primo(n,k+1)
Resultado
![Page 28: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/28.jpg)
Ejercicio 1.5
n 5
k 4
Primo(n,k+1) cierto
Resultado
n 5
k 5
Primo(n,k+1)
Resultado
![Page 29: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/29.jpg)
Ejercicio 1.5
n 5
k 3
Primo(n,k+1) cierto
Resultado
n 5
k 2
Primo(n,k+1)
Resultado
EsPrimo(5)
n 5
Primo(n,2)
Resultado
n 5
k 4
Primo(n,k+1) cierto
Resultado
![Page 30: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/30.jpg)
Ejercicio 1.5
n 5
k 2
Primo(n,k+1) cierto
Resultado
EsPrimo(5)
n 5
Primo(n,2)
Resultado
n 5
k 3
Primo(n,k+1) cierto
Resultado
![Page 31: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/31.jpg)
Ejercicio 1.5
EsPrimo(5)
n 5
Primo(n,2) cierto
Resultado
n 5
k 2
Primo(n,k+1) cierto
Resultado
![Page 32: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/32.jpg)
Ejercicio 1.5
EsPrimo(5) cierto
n 5
Primo(n,2) cierto
Resultado
![Page 33: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/33.jpg)
Ejercicio 1.5
EsPrimo(5) cierto
![Page 34: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/34.jpg)
Ejercicio: Fibonacci
• La serie Fibonacci empieza por
1 1 2 3 5 8 13 21 34 55 …
• Tiene una definición recursiva:
F(0) = 1
F(1) = 1
F(n) = F(n-2) + F(n-1), n > 1
![Page 35: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/35.jpg)
Fibonacci
funcion F(n:natural) devuelve natural
si (n <= 1) entonces
devuelve 1;
sino
devuelve F(n-2)+F(n-1);
fsi
ffuncion
![Page 36: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/36.jpg)
Ejercicio: Fibonacci
• Usar la pila para interpretar el resultado de F(4)
![Page 37: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/37.jpg)
Ejercicio: Fibonacci
F(4)
![Page 38: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/38.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2)
F(n-1)
Resultado
![Page 39: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/39.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2)
F(n-1)
Resultado
n 2
F(n-2)
F(n-1)
Resultado
![Page 40: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/40.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2)
F(n-1)
Resultado
n 2
F(n-2)
F(n-1)
Resultado
n 0
F(n-2)
F(n-1)
Resultado
![Page 41: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/41.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2)
F(n-1)
Resultado
n 2
F(n-2) 1
F(n-1)
Resultado
n 0
F(n-2)
F(n-1)
Resultado
![Page 42: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/42.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2)
F(n-1)
Resultado
n 2
F(n-2) 1
F(n-1)
Resultado
n 1
F(n-2)
F(n-1)
Resultado
![Page 43: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/43.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2)
F(n-1)
Resultado
n 2
F(n-2) 1
F(n-1) 1
Resultado
n 1
F(n-2)
F(n-1)
Resultado
![Page 44: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/44.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 2
F(n-2) 1
F(n-1) 1
Resultado
![Page 45: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/45.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2)
F(n-1)
Resultado
![Page 46: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/46.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2)
F(n-1)
Resultado
n 1
F(n-2)
F(n-1)
Resultado
![Page 47: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/47.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2) 1
F(n-1)
Resultado
n 1
F(n-2)
F(n-1)
Resultado
![Page 48: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/48.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2) 1
F(n-1)
Resultado
n 2
F(n-2)
F(n-1)
Resultado
![Page 49: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/49.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2) 1
F(n-1)
Resultado
n 2
F(n-2)
F(n-1)
Resultado
n 0
F(n-2)
F(n-1)
Resultado
![Page 50: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/50.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2) 1
F(n-1)
Resultado
n 2
F(n-2) 1
F(n-1)
Resultado
n 0
F(n-2)
F(n-1)
Resultado
![Page 51: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/51.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2) 1
F(n-1)
Resultado
n 2
F(n-2) 1
F(n-1)
Resultado
n 1
F(n-2)
F(n-1)
Resultado
![Page 52: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/52.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2) 1
F(n-1)
Resultado
n 2
F(n-2) 1
F(n-1) 1
Resultado
n 1
F(n-2)
F(n-1)
Resultado
![Page 53: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/53.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1)
Resultado
n 3
F(n-2) 1
F(n-1) 2
Resultado
n 2
F(n-2) 1
F(n-1) 1
Resultado
![Page 54: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/54.jpg)
Ejercicio: Fibonacci
F(4)
n 4
F(n-2) 2
F(n-1) 3
Resultado
n 3
F(n-2) 1
F(n-1) 2
Resultado
![Page 55: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/55.jpg)
Ejercicio: Fibonacci
F(4) 5
n 4
F(n-2) 2
F(n-1) 3
Resultado
![Page 56: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/56.jpg)
Ejercicio: Fibonacci
F(4) 5
![Page 57: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/57.jpg)
Tipos de recursividad
Recursividad Directa Indirecta
Simple
Múltiple
F(x)
F(x) G(x)F(x)
G(x)F(x)
![Page 58: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/58.jpg)
Recursividad indirecta
• Determinar si un número natural n es par– caso base: n = 0 es un número par– caso recursivo: n es par si n – 1 es impar
• Determinar si un número natural n es impar– caso base: n = 0 no es un número impar– caso recursivo: n es impar si n – 1 es par
![Page 59: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/59.jpg)
Par e impar
funcion Par(n:natural) devuelve booleanosi (n = 0) entonces
devuelve cierto;sino devuelve Impar(n – 1); fsi ffuncion
funcion Impar(n:natural) devuelve booleanosi (n = 0) entonces
devuelve falso;sino devuelve Par(n – 1); fsi ffuncion
![Page 60: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/60.jpg)
Tipos de recursividad
Recursividad Directa Indirecta
Simple
Factorial(n)
Suma(V,i,n)
Primo(n,k)
Par(n) – Impar(n)
Múltiple
Fibonacci(n)
![Page 61: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/61.jpg)
Transformación
• Todo algoritmo recursivo se puede transformar en un algoritmo iterativo (con bucles)
• Más difícil para recursividad múltiple y/o indirecto
• No obstante, para recursividad simple y directo hay una transformación general
![Page 62: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/62.jpg)
Función recursiva
funcion Recursiva(x:tipo) devuelve tipo
si B(x) entonces
devuelve S;
sino
devuelve F(x, Recursiva(T(x)));
fsi
ffuncion
x: parámetros T(x): llamada recursiva
B(x): condición F(x,y): acción recursiva
S: acción caso base
![Page 63: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/63.jpg)
Función equivalente iterativa
funcion Iterativa(x:tipo) devuelve tipo
resultado S;mientras no(B(x)) hacer
resultado F(x, resultado); x T(x);fmientras
devuelve resultado;
ffuncion
![Page 64: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/64.jpg)
Ejemplo: Factorial
funcion Factorial(n:natural) devuelve natural
si (n = 0) entonces
devuelve 1;
sino
devuelve n*Factorial(n-1);
fsi
ffuncion
x: n T(x): n - 1
B(x): n = 0 F(x,y): n*y
S: 1
![Page 65: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/65.jpg)
Función equivalente iterativa
funcion Factorial(n:natural) devuelve natural
resultado 1;mientras no(n = 0) hacer
resultado n*resultado; n n - 1;fmientras
devuelve resultado;
ffuncion
![Page 66: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/66.jpg)
Ejemplo: Primo
funcion Primo(n,k:natural) devuelve booleanosi (k >= n) entonces
devuelve cierto; sino si (n mod k = 0) entonces devuelve falso; sino devuelve Primo(n,k+1); fsiffuncion
x: n, k T(x): n, k+1B(x): k >= n F(x,y): si (n mod k = 0) falsoS: cierto sino y
![Page 67: Recurrencia Programación II 27-28 de enero de 2009](https://reader036.vdocumento.com/reader036/viewer/2022062323/5665b4731a28abb57c918f6c/html5/thumbnails/67.jpg)
Función equivalente iterativa
funcion Primo(n,k:natural) devuelve booleanoresultado cierto;mientras no(k >= n) hacer
si (n mod k = 0) entonces resultado falso; sino resultado resultado; n n; k k + 1;fmientrasdevuelve resultado;
ffuncion