![Page 1: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/1.jpg)
PROGRAMACIÓN DECLARATIVAPROGRAMACIÓN DECLARATIVA
UNIVERSIDAD DE CÓRDOBA
ESCUELA POLITÉCNICA SUPERIOR DE CÓRDOBA
DEPARTAMENTO DEINFORMÁTICA Y ANÁLISIS NUMÉRICO
PROGRAMACIÓN DECLARATIVAPROGRAMACIÓN DECLARATIVAINGENIERÍA INFORMÁTICA
CUARTO CURSO
PRIMER CUATRIMESTRE
Tema 4.- Recursión e iteración
![Page 2: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/2.jpg)
Primera parte:
Scheme
Tema 1.- Introducción al Lenguaje Scheme
Tema 2.- Expresiones y Funciones
Tema 3.- Predicados y sentencias condicionales
Tema 4.- Iteración y Recursión
Tema 5.- Tipos de Datos Compuestos
Tema 6.- Abstracción de Datos
PROGRAMACIÓN DECLARATIVA PROGRAMACIÓN DECLARATIVA PROGRAMAPROGRAMA
2
Tema 6.- Abstracción de Datos
Tema 7.- Lectura y Escritura
Tema 8.- Introducción al Lenguaje Prolog
Tema 9.- Elementos Básicos de Prolog
Tema 10.- Listas
Tema 11.- Reevaluación y el “corte”
Tema 12.- Entrada y Salida
Segunda parte: Prolog
![Page 3: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/3.jpg)
Primera parte: Scheme
PROGRAMACIÓN DECLARATIVA PROGRAMACIÓN DECLARATIVA PROGRAMAPROGRAMA
Tema 1.- Introducción al Lenguaje Scheme
Tema 2.- Expresiones y Funciones
Tema 3.- Predicados y sentencias condicionales
3
Tema 4.- Iteración y Recursión
Tema 5.- Tipos de Datos Compuestos
Tema 6.- Abstracción de Datos
Tema 7.- Lectura y Escritura
![Page 4: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/4.jpg)
Índice
1. Forma especial iterativa “do”
2. Recursión
Programación Declarativa Tema 4.- Recursión e iteración
4
3. Funciones pasadas como parámetros
4. Funciones devueltas como resultados
![Page 5: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/5.jpg)
Índice
1. Forma especial iterativa “do”
2. Recursión
Programación Declarativa Tema 4.- Recursión e iteración
5
3. Funciones pasadas como parámetros
4. Funciones devueltas como resultados
![Page 6: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/6.jpg)
1. Forma especial iterativa “do”
• Sintaxis(do
;; Inicializaciones((<variable 1> <inicialización 1> <paso 1>)(<variable 2> <inicialización 2> <paso 2>)
…(<variable n> <inicialización n> <paso n>)
6
(<variable n> <inicialización n> <paso n>));; Condición de salida y sentencias asociadas( <condición> <sentencia> …)
;; Cuerpo del bucle<sentencia> …
)
![Page 7: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/7.jpg)
Inicializaciones
Sentencias de salidaCondición
Verdadero *
Falso
1. Forma especial iterativa “do”
• Significado
7
Cuerpo del bucle
Pasos
![Page 8: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/8.jpg)
1. Forma especial iterativa “do”
• Semántica
o El ámbito de cada variable_i abarca el cuerpo del bucle do y las sentencias de paso.
o La evaluación de las sentencias de inicializaciónse realiza en un orden no determinado
o La variable_i no puede usarse en las sentencias de
8
o La variable_i no puede usarse en las sentencias de inicialización.
o Las sentencias de paso pueden usar los valores de las variables que tengan en el paso anterior.
o La evaluación de las sentencias de paso se realiza en un orden no determinado.
![Page 9: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/9.jpg)
1. Forma especial iterativa “do”
• Ejemplo (1/9): factorial
≥−×
=∨===
21
10 1
i n)! s(nn
)(n)si (n n!f(n)
9
≥−× 21 i n)! s(nn
![Page 10: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/10.jpg)
1. Forma especial iterativa “do”
• Ejemplo (2/9): factorial (versión nº 1)
(define (factorial-con-set n)(if (= n 0) 1
(do;; Inicializaciones
((i n (- i 1))
10
(i n (- i 1))(resultado 1) ;; no tiene “paso”
);; Condición y sentencia de salida((= i 1) resultado);; Cuerpo del bucle(set! resultado (* resultado i))
))
) Se recomienda evitar el uso de set!
![Page 11: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/11.jpg)
1. Forma especial iterativa “do”
• Ejemplo (3/9): factorial (versión nº 2)
(define (factorial n)(if (= n 0) 1
(do ;; Inicializaciones(
(i n (- i 1))
11
(i n (- i 1))(resultado 1 (* resultado i))
);; Condición y sentencia de salida((= i 1) resultado);; no hay cuerpo del bucle
))
![Page 12: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/12.jpg)
1. Forma especial iterativa “do”
• Ejemplo (4/9): Fibonacci
≥−−
=∨==
) Si n)+f(nf(n
n Si n f(n)
221
10 1
12
≥−− ) Si n)+f(nf(n 221
![Page 13: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/13.jpg)
1. Forma especial iterativa “do”
• Ejemplo (5/9): Fibonacci
(define (fib-iter n)
(if (or (= n 0) (= n 1)) 1(do
;; Inicializaciones( (actual 1 (+ actual anterior))
13
(actual 1 (+ actual anterior))(anterior 1 actual)(i n (- i 1)
);; Condición y sentencia de salida
((= i 1) actual);; no hay cuerpo del bucle)
))
![Page 14: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/14.jpg)
1. Forma especial iterativa “do”
• Ejemplo: series no paramétricas
11111112π
∑∞
333333 )1(...)2()1( bbaaan
b
an
+−++++++=∑=
14
69
1
4
1
1
1
3
1
2
1
1
112
2221
2
π......
nn
=+++=+++=∑∞
=
8119
1
75
1
31
1
2
1
4
1
π + . . .
+
+
)(nnnn
n
=×××
=+×
∑∞
+=
=
![Page 15: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/15.jpg)
1. Forma especial iterativa “do”
• Ejemplo (4/9)
(define (sumar-cubos inicial final)(define (cubo x)
(* x x x))
(do ;; variables((i inicial (+ i 1))
333333 )1(...)2()1( bbaaan
b
an
+−++++++=∑=
15
(i inicial (+ i 1))(resultado 0.0 (+ resultado (cubo i)))
);; Condición y sentencia de salida((> i final) resultado);; No hay cuerpo)
)(suma-cubos 1 3) � 36
![Page 16: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/16.jpg)
1. Forma especial iterativa “do”
• Ejemplo (5/9)
(define (sumar-reciprocos-cuadrados-perfectos final)
(define (termino n)(/ 1.0 (* n n)))
;;
69
1
4
1
1
1
3
1
2
1
1
112
2221
2
π......
nn
=+++=+++=∑∞
=
16
;;(do (
(i 1.0 (+ i 1))(resultado 0.0 (+ resultado (termino i)))
);; Condición de salida: número de elementos((> i final) resultado);; No hay cuerpo)
)(sumar-reciprocos-cuadrados-perfectos 1000) � 1,6449…
![Page 17: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/17.jpg)
1. Forma especial iterativa “do”
• Ejemplo(6/9)
(define (sumar-pi-octavos-v1 cota)(define (termino n)
(/ 1.0 (* n (+ n 2))))
;;(do (
(i 1.0 (+ i 4))
8119
1
75
1
31
1
2
1
4
1
π + . . .
+
+
)(nnnn
n
=×××
=+×
∑∞
+=
=
17
(i 1.0 (+ i 4))(resultado 0.0 (+ resultado (termino i)))
);;((< (termino i) cota) resultado);; No hay cuerpo)
)
(* 8.0 (sumar-pi-octavos-v1 0.00001)) � 3.135263603…
![Page 18: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/18.jpg)
1. Forma especial iterativa “do”
• Ejemplo(6/9)
(define (sumar-pi-octavos-v1 cota)(define (termino n)
(/ 1.0 (* n (+ n 2))))
;;(do (
(i 1.0 (+ i 4))
Ineficiencia
8119
1
75
1
31
1
2
1
4
1
π + . . .
+
+
)(nnnn
n
=×××
=+×
∑∞
+=
=
18
(i 1.0 (+ i 4))(resultado 0.0 (+ resultado (termino i)))
);;((< (termino i) cota) resultado);; No hay cuerpo)
)
(* 8.0 (sumar-pi-octavos-v1 0.00001)) � 3.135263603…
![Page 19: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/19.jpg)
1. Forma especial iterativa “do”
• Ejemplo(7/9)
(define (sumar-pi-octavos-v2 cota)(define (termino n)
(/ 1.0 (* n (+ n 2))))
;;(do (
(i 5.0 (+ i 4))
8119
1
75
1
31
1
2
1
4
1
π + . . .
+
+
)(nnnn
n
=×××
=+×
∑∞
+=
=
19
(i 5.0 (+ i 4))(valor (termino 1) (termino i))(resultado 0.0 (+ resultado valor))
);; Condición y sentencia de salida((< valor cota) resultado);; No hay cuerpo)
)(* 8.0 (sumar-pi-octavos-v2 0.00001)) � 3.135263603…
![Page 20: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/20.jpg)
1. Forma especial iterativa “do”
• Ejemplo(8/9)
8119
1
75
1
31
1
2
1
4
1
π + . . .
+
+
)(nnnn
n
=×××
=+×
∑∞
+=
=
20
La serie anterior es equivalente a la serie
8119
1
75
1
31
1
1434
1
1
π + . . .
+
+
)n()n(n
=×××
=−×−
∑∞
=
![Page 21: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/21.jpg)
1. Forma especial iterativa “do”
• Ejemplo(8/9)
(define (sumar-pi-octavos-v3 cota)(define (termino n)
(/ 1.0 (* (- (* 4 n) 3) (- (* 4 n) 1) )
))(do (
8119
1
75
1
31
1
1434
1
1
π + . . .
+
+
)n()n(n
=×××
=−×−
∑∞
=
21
(do ((i 2.0 (+ i 1))(valor (termino 1) (termino i))(resultado 0.0 (+ resultado valor))
);; Condición y sentencia de salida((< valor cota) resultado);; No hay cuerpo)
)
![Page 22: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/22.jpg)
1. Forma especial iterativa “do”
• Ejemplo: series paramétricas
n
nn
)!n(
x)(- seno(x) ∑
∞
=
+
+=
0
12
121
22
n )!n(∑
= +0 12
![Page 23: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/23.jpg)
1. Forma especial iterativa “do”
• Ejemplo (9/9): series paramétricas
(define (serie-seno x iteraciones)(define (termino x n)(* (expt -1 n)
(/ (expt x (+ (* 2 n) 1))(factorial (+ (* 2 n) 1))
))
)
n
nn
)!n(
x)(- seno(x) ∑
∞
=
+
+=
0
12
121
23
);;(do (
(n 0 (+ n 1))(resultado 0.0 (+ resultado (termino x n)))
);;((> n iteraciones) resultado);; No hay cuerpo)
)
![Page 24: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/24.jpg)
Índice
1. Forma especial iterativa “do”
2. Recursión
Programación Declarativa Tema 4.- Recursión e iteración
24
3. Funciones pasadas como parámetros
4. Funciones devueltas como resultados
![Page 25: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/25.jpg)
2. Recursión
• Descripción
• Recursión simple
• Recursión múltiple
• Recursión de cola
• Forma especial “let con nombre”
25
![Page 26: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/26.jpg)
2. Recursión
• Descripción
• Recursión simple
• Recursión múltiple
• Recursión de cola
• Forma especial “let con nombre”
26
![Page 27: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/27.jpg)
2. Recursión
• Descripción
o Una función es “recursiva” si se llama a sí misma
o Fases para definir una función recursiva
1. Determinar cómo realizar un paso.
2. Descomponer el problema en un paso y en un sub-problema idéntico más simple.
27
sub-problema idéntico más simple.
3. Determinar cuándo se ha de parar la ejecución de la función.
![Page 28: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/28.jpg)
2. Recursión
• Descripción
• Recursión simple
• Recursión múltiple
• Recursión de cola
• Forma especial “let con nombre”
28
![Page 29: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/29.jpg)
2. Recursión
• Recursión simple
o Una función posee recursividad simple
� si solamente puede llamarse a sí misma una única vez, a lo sumo
� por cada línea de ejecución.
29
o Línea de ejecución
� Sucesión de sentencias que se pueden ejecutarconsecutivamente dentro de una función
![Page 30: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/30.jpg)
2. Recursión
• Recursión simple
o Ejemplo (1/7)
� Factorial (versión recursiva): n ∈ N
≥−×
=∨===
21
10 1
i n)! s(nn
)(n)si (n n!f(n)
30
≥−×==
21 i n)! s(nn
![Page 31: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/31.jpg)
2. Recursión
• Recursión simple
o Ejemplo (1/7)
� Factorial (versión recursiva): n ∈ N
(define (factorial n)(if (or (= n 0) (= n 1))
1
31
(if (or (= n 0) (= n 1))1(* n (factorial (- n 1)))
))
(factorial 4) � 24
![Page 32: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/32.jpg)
2. Recursión
• Recursión simple
o Ejemplo (2/7)
� Potencia: a ∈ R, b ∈ N
=
0=b Si
ab
1
32
≥×
=
− 1 b Si aa
ab
b
1
![Page 33: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/33.jpg)
2. Recursión
• Recursión simple
o Ejemplo (2/7)
� Potencia: a ∈ R, b ∈ N
(define (potencia a b)(if (= b 0)
1
33
(if (= b 0)1(* a (potencia a (- b 1)))
))
(potencia 2 3) � 8
![Page 34: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/34.jpg)
2. Recursión
• Recursión simple
o Ejemplo (3/7)
(define (suma-cubos inicial final);; función auxiliar
(define (cubo x) (* x x x));; cuerpo de suma-cubos
333333 121 b)(b...)(a)(aan
b
an
+−++++++=∑=
34
;; cuerpo de suma-cubos(if (> inicial final)
0(+
(cubo inicial)(suma-cubos (+ inicial 1) final)
))
)(suma-cubos 1 3) � 36
![Page 35: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/35.jpg)
2. Recursión
• Recursión simple
o Ejemplo: series no paramétricas
69
1
4
1
1
1
3
1
2
1
1
112
2221
2
π......
nn
=+++=+++=∑∞
=
35
8119
1
75
1
31
1
1434
1
1
π + . . .
+
+
)n()n(n
=×××
=−×−
∑∞
=
8119
1
75
1
31
1
2
1
4
1
π + . . .
+
+
)(nnnn
n
=×××
=+×
∑∞
+=
=
![Page 36: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/36.jpg)
2. Recursión
• Recursión simple
o Ejemplo (4/7)
(define (suma-reciprocos-cuadrados-perfectos n)(define (termino n)
69
1
4
1
1
1
3
1
2
1
1
112
2221
2
π......
nn
=+++=+++=∑∞
=
36
(define (termino n)(/ 1.0 (* n n))
)(if (<= n 0) 0.0
(+ (termino n)(suma-reciprocos-cuadrados-perfectos (- n 1))
))
)
![Page 37: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/37.jpg)
2. Recursión• Recursión simple
o Ejemplo (5/7)
(define (suma-pi-octavos-v1 n)
(define (termino n)(/ 1.0 (* n (+ n 2)))
)(define (auxiliar-suma-pi-octavos i n)(if (> i n)
8119
1
75
1
31
1
2
1
4
1
π + . . .
+
+
)(nnnn
n
=×××
=+×
∑∞
+=
=
37
(if (> i n)0.0(+ (termino i)
(auxiliar-suma-pi-octavos (+ i 4) n))
));; Llamada a la función auxiliar(auxiliar-suma-pi-octavos 1 n)
)
![Page 38: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/38.jpg)
2. Recursión• Recursión simple
o Ejemplo (6/7)(define (suma-pi-octavos-v2 n)
(define (termino n)(/ 1.0
(* (- (* 4 n) 3) (- (* 4 n) 1) ))
)(define (auxiliar-suma-pi-octavos i n)
8119
1
75
1
31
1
1434
1
1
π+. . .
+
+
)n()n(n
=×××
=−×−
∑∞
=
38
(define (auxiliar-suma-pi-octavos i n)(if (> i n) 0.0
(+ (termino i)(auxiliar-suma-pi-octavos (+ i 1) n)
))
);; Llamada a la función auxiliar(auxiliar-suma-pi-octavos 1 n)
)
![Page 39: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/39.jpg)
2. Recursión• Recursión simple
o Ejemplo (7/7): serie paramétrica
(define (serie-seno x n)(define (termino x n)
(* (expt -1 n)(/ (expt x (+ (* 2 n) 1))
(factorial (+ (* 2 n) 1))
n
nn
)!n(
x)(- seno(x) ∑
∞
=
+
+=
0
12
121
39
(factorial (+ (* 2 n) 1)))
))
;;(if (< n 0)
0.0(+ (termino x n) (serie-seno x (- n 1))))
)
![Page 40: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/40.jpg)
2. Recursión
• Descripción
• Recursión simple
• Recursión múltiple
• Recursión de cola
• Forma especial “let con nombre”
40
![Page 41: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/41.jpg)
2. Recursión
• Recursión múltiple
o Una función posee recursividad múltiple si
� puede llamarse a sí misma más de una vez
� en una misma línea de ejecución, al menos.
41
![Page 42: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/42.jpg)
2. Recursión
• Recursión múltiple
o Ejemplo (1/2)
� Fibonacci (versión recursiva doble)
=∨= n Si n 10 1
42
≥−−
=∨==
) Si n)+f(nf(n
n Si n f(n)
221
10 1
![Page 43: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/43.jpg)
2. Recursión
• Recursión múltiple
o Ejemplo (1/2)
� Fibonacci (versión recursiva doble)
(define (fibonacci n)(if (or (= n 0) (= n 1))
1
43
1(+
(fibonacci (- n 1))(fibonacci (- n 2))
))
)
(fibonacci 4) � 5
![Page 44: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/44.jpg)
2. Recursión
• Recursión múltiple
o Ejemplo (1/2)
� Fibonacci (versión recursiva doble)
� Árbol de activación
(fibonacci 4)
44
(fibonacci 3) (fibonacci 2)
(fibonacci 2) (fibonacci 1) (fibonacci 1) (fibonacci 0)
(fibonacci 1) (fibonacci 0)
![Page 45: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/45.jpg)
2. Recursión
• Recursión múltiple
o Ejemplo (1/2)
� Fibonacci (versión recursiva doble)
� Árbol de activación
(fibonacci 4)
Ineficiencia de la recursión múltiple: repetición de cálculos
45
(fibonacci 3) (fibonacci 2)
(fibonacci 2) (fibonacci 1) (fibonacci 1) (fibonacci 0)
(fibonacci 1) (fibonacci 0)
![Page 46: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/46.jpg)
2. Recursión
• Recursión múltiple
o Ejemplo (2/2)
� Torres de Hanoi
A C B
46
![Page 47: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/47.jpg)
2. Recursión
• Recursión múltiple
o Ejemplo (2/2)
� Torres de Hanoi: objetivo
� Trasladar todos los discos desde la varilla Ahasta la varilla B
� Se deben respetar las reglas de los
47
� Se deben respetar las reglas de losmovimientos
� Se puede utilizar la varilla auxiliar C
![Page 48: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/48.jpg)
2. Recursión
• Recursión múltiple
o Ejemplo (2/2)
� Torres de Hanoi: reglas
1. Todos los discos son de tamañosdiferentes.
2. Inicialmente cada uno de los discos
48
2. Inicialmente cada uno de los discosdescansa sobre uno mayor.
3. Sólo se puede mover un disco cada vez.
4. Ningún disco se puede colocar sobre unomás pequeño.
![Page 49: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/49.jpg)
• Torres de Hanoi(define (Hanoi n a b c)
(define (cambio x y)(display x)(display " --> ")(display y)(display "; ")1
)
49
);; cuerpo de “Hanoi”(if (= n 1) (cambio a b)(+
(Hanoi (- n 1) a c b)(cambio a b)(Hanoi (- n 1) c b a)
))
)
![Page 50: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/50.jpg)
• Torres de Hanoi
(Hanoi 3 A B C)
(Hanoi 2 A C B) (cambio A B) (Hanoi 2 C B A)
Árbol de activación
50
(Hanoi 1 A B C) (cambio A C) (Hanoi 1 B C A) (Hanoi 1 C A B) (cambio C B) (Hanoi 1 A B C)
(cambio A B) (cambio B C) (cambio C A) (cambio A B)
![Page 51: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/51.jpg)
• Torres de Hanoi
(Hanoi 3 A B C)
(Hanoi 2 A C B) (cambio A B) (Hanoi 2 C B A)
Recorrido en profundidad
51
(Hanoi 1 A B C) (cambio A C) (Hanoi 1 B C A) (Hanoi 1 C A B) (cambio C B) (Hanoi 1 A B C)
(cambio A B) (cambio B C) (cambio C A) (cambio A B)
![Page 52: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/52.jpg)
2. Recursión
• Recursión múltiple
o Ejemplo (2/2)
� Torres de Hanoi: 7 movimientos
1. A � B
2. A � C
52
3. B � C
4. A � B
5. C � A
6. C � B
7. A � B
![Page 53: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/53.jpg)
2. Recursión
• Descripción
• Recursión simple
• Recursión múltiple
• Recursión de cola
• Forma especial “let con nombre”
53
![Page 54: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/54.jpg)
2. Recursión
• Recursión de cola
o Concepto de “reducción”
o Definición de “recursión de cola”
o Ejemplo
o Comparación
54
o Más ejemplos
![Page 55: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/55.jpg)
2. Recursión
• Recursión de cola
o Concepto de “reducción”
� Transformación de un problema en otro mássimple
� que no requiere ningún cálculo adicional cuando haya sido resuelto.
55
cuando haya sido resuelto.
![Page 56: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/56.jpg)
2. Recursión
• Recursión de cola
o Definición de “recursión de cola”
� Una función es recursiva de cola si todas sustransformaciones son reducciones
� Término en inglés: “tail recursive”
56
![Page 57: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/57.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (1/5)
� Factorial
=∨=
==10 1 )(n)si (n
n!f(n)
57
≥−×
=∨===
21
10 1
i n)! s(nn
)(n)si (n n!f(n)
![Page 58: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/58.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (1/5)
� Factorial
(define (fac-cola n);; función auxiliar(define (fac-aux n resultado)
58
(define (fac-aux n resultado)(if (= n 0) resultado
(fac-aux (- n 1) (* n resultado)))
);; cuerpo de “fac-cola”(fac-aux n 1)
)
(fac-cola 4) � 24
![Page 59: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/59.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (1/5)
� Factorial
� Proceso “recursivo de cola”
(fac-cola 4)
59
(fac-cola 4)
(fac-aux 4 1)(fac-aux 3 4) (fac-aux 2 12)(fac-aux 1 24)(fac-aux 0 24)
24
![Page 60: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/60.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (1/5)
� Factorial
� Proceso “recursivo lineal”(factorial 4) (* 4 (factorial 3))
60
(* 4 (factorial 3))(* 4 (* 3 (factorial 2)))(* 4 (* 3 (* 2 (factorial 1))))(* 4 (* 3 (* 2 (* 1 (factorial 0)))))(* 4 (* 3 (* 2 (* 1 1))))(* 4 (* 3 (* 2 1)))(* 4 (* 3 2))(* 4 6)24
Expansión
Contracción
![Page 61: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/61.jpg)
2. Recursión
• Recursión de cola
o Comparación
� Proceso “recursivo lineal”
� Proceso “recursivo de cola”
61
![Page 62: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/62.jpg)
2. Recursión
• Recursión de cola
o Comparación
� Proceso “recursivo lineal”
� Expansión
� Se efectúan las llamadas recursivas
62
� Se encadenan una serie de operaciones“diferidas”
� Contracción
� Evalúa las operaciones “diferidas”
![Page 63: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/63.jpg)
2. Recursión
• Recursión de cola
o Comparación
� Proceso “recursivo lineal”
� Observación
� El intérprete debe
63
� almacenar los operadores yargumentos de las operacionesdiferidas
� recordar el orden en el que se debenevaluar dichas operaciones diferidas
![Page 64: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/64.jpg)
2. Recursión
• Recursión de cola
o Comparación
� Proceso “recursivo lineal”
� Observación
� Necesita conocer información adicional“escondida”
64
“escondida”
� mantenida por el intérprete
� no contenida en las variables
� Está información indica qué operacionesdiferidas están pendientes de realizar
![Page 65: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/65.jpg)
2. Recursión
• Recursión de cola
o Comparación
� Proceso “recursivo de cola”
� Las variables del programa suministran unadescripción completa del estado en el quese encuentra el proceso en cualquier
65
se encuentra el proceso en cualquierinstante.
� En cada paso, el número de operaciones esconocido “a priori”.
� No necesita “operaciones diferidas”
![Page 66: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/66.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (2/5)
(define (suma-reciprocos-cuadrados-perfectos n)(define (termino n)
(/ 1.0 (* n n)))
69
1
4
1
1
1
3
1
2
1
1
112
2221
2
π......
nn
=+++=+++=∑∞
=
66
)(define (auxiliar n resultado)
(if (<= n 0)resultado(auxiliar (- n 1) (+ resultado (termino n)))
))
;; Llamada a la función auxiliar(auxiliar n 0.0))
![Page 67: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/67.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (3/5)
(define (suma-pi-octavos n)
(define (termino n)(/ 1.0
(* (- (* 4 n) 3) (- (* 4 n) 1) ))
8119
1
75
1
31
1
1434
1
1
π+ . . .
+
+
)n()n(n
=×××
=−×−
∑∞
=
67
))
(define (auxiliar i n resultado)(if (> i n) resultado
(auxiliar (+ i 1) n (+ resultado (termino i)))));; Llamada a la función auxiliar(auxiliar 1 n 0.0)
)
![Page 68: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/68.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (4/5)(define (serie-seno x n)(define (termino x n)
(* (expt -1 n)(/ (expt x (+ (* 2 n) 1)) (factorial (+ (* 2 n) 1)) ))
)
n
nn
)!n(
x)(- seno(x) ∑
∞
=
+
+=
0
12
121
68
)(define (auxiliar x n resultado)
(if (< n 0)resultado(auxiliar x (- n 1) (+ (termino x n) resultado)))
);; Llamada a la función auxiliar(auxiliar x n 0.0)
)
![Page 69: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/69.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (5/5)
� Raíz cuadrada usando el método de Newton
1x 0 =
69
1n si 2
xnxn
x
x 1n ≥
+
=+
x = y x n lim
n
=
∞→
![Page 70: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/70.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (5/5)
� Raíz cuadrada usando el método de Newton
2y = 1.0x0 =
70
2y = 1.0x0 =
![Page 71: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/71.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (5/5)
� Raíz cuadrada usando el método de Newton
2y = 1.0x0 = 1.52
11
2
x 1 =
+
=
71
2y = 1.0x0 = 1.52
x 1 ==
![Page 72: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/72.jpg)
2y =
2. Recursión
• Recursión de cola
o Ejemplo (5/5)
� Raíz cuadrada usando el método de Newton
1.0x0 = 1.52
11
2
x 1 =
+
=2y =
72
1.0x0 = 1.52
x 1 ==
61.412
1.51.5
2
x 2
)=
+
=
![Page 73: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/73.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (5/5)
� Raíz cuadrada usando el método de Newton
2y = 1.0x0 = 1.52
11
2
x 1 =
+
=
73
2y = 1.0x0 = 1.52
x 1 ==
61.412
1.51.5
2
x 2
)=
+
=
1.414215682
61.4161.41
2
x 3 =
+
=
))
![Page 74: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/74.jpg)
2. Recursión
• Recursión de cola
o Ejemplo (5/5)
� Raíz cuadrada usando el método de Newton
2y = 1.0x0 = 1.52
11
2
x 1 =
+
=
74
2y = 1.0x0 = 1.52
x 1 ==
61.412
1.51.5
2
x 2
)=
+
=
1.414215682
61.4161.41
2
x 3 =
+
=
))
![Page 75: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/75.jpg)
• Ejemplo (5/5)
o Raíz cuadrada usando el método de Newton(define (raíz x cota_error)
(define (siguiente x y)(/ (+ (/ x y) y) 2. )
)(define (raíz-aux x y)
(if (< (abs (- (* y y) x)) cota_error)y
75
y(raíz-aux x (siguiente x y))
));; cuerpo de “raíz”: llamada a la función auxiliar(raíz-aux x 1.0)
)
(raíz 2 0.001) � 1.41421568
![Page 76: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/76.jpg)
• Ejemplo (5/5)
o Raíz cuadrada usando el método de Newton
(raíz 2 0.001)
(raíz-aux 2 1.0)
(raíz-aux 2 1.5)
76
(raíz-aux 2 1.41666…)
(raíz-aux 2 1.41411568)
� 1.41421568
![Page 77: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/77.jpg)
2. Recursión
• Descripción
• Recursión simple
• Recursión múltiple
• Recursión de cola
• Forma especial “let con nombre”
77
• Forma especial “let con nombre”
![Page 78: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/78.jpg)
2. Recursión
• Forma especial “let con nombre”
o Sintaxis
(let <nombre-función> ;; Asignación inicial a los parámetros
((<parámetro 1> <inicialización 1>)
78
(<parámetro 1> <inicialización 1>)(<parámetro 2> <inicialización 2>)
… (<parámetro n> <inicialización n>)
);; cuerpo del “let con nombre”,;; se puede llamar recursivamente a ;; <nombre-función>
<sentencia> …)
![Page 79: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/79.jpg)
2. Recursión
• Forma especial “let con nombre”
o Significado
� Se evalúan en un orden no determinado las sentencias de inicialización de los parámetros
� Se ejecuta el cuerpo de “let con nombre”
79
� Si hay una llamada recursiva entonces los valores de los argumentos reales se asignan a los parámetros de let.
� Término en inglés: named let
![Page 80: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/80.jpg)
2. Recursión
• Forma especial “let con nombre”
o Ejemplo(define (factorial-let-nombre n)
(let fact-let;; Asignación inicial a los parámetros(
(i n) (resultado 1)
80
(resultado 1));; cuerpo de let con nombre(if (or (= i 0) (= i 1))
resultado;; llamada recursiva(fact-let (- i 1) (* resultado i))
))
)
![Page 81: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/81.jpg)
Índice
1. Forma especial iterativa “do”
2. Recursión
Programación Declarativa Tema 4.- Recursión e iteración
81
3. Funciones pasadas como parámetros
4. Funciones devueltas como resultados
![Page 82: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/82.jpg)
3. Funciones pasadas como parámetros
• Descripción
• Ejemplos
• Aplicaciones
82
![Page 83: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/83.jpg)
3. Funciones pasadas como parámetros
• Descripción
• Ejemplos
• Aplicaciones
83
![Page 84: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/84.jpg)
3. Funciones pasadas como parámetros
• Descripción
o Función f que recibe una función g como parámetro formal
(define (f pf1 pf2 … pfi g pfi+1 … pfn)
<cuerpo de f>
)
84
)
donde pf1, pf2,…, pfi , g, pfi+1 , …, pfn
son los parámetros formales de f
o Observación
� Solamente hay que poner un nombre al parámetro formal que va a actuar como función
![Page 85: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/85.jpg)
3. Funciones pasadas como parámetros
• Descripción
o Uso de g dentro de la función f
(g x1 x2 … xk)
donde x1, x2 , … , xk
son los parámetros reales de g
85
o Observación
� Solamente hay que llamar a la función con los parámetros reales que le correspondan.
![Page 86: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/86.jpg)
3. Funciones pasadas como parámetros
• Descripción
o Paso de una función como parámetro de otra función f
1. Función definida previamente
2. Función creada con lambda
86
![Page 87: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/87.jpg)
3. Funciones pasadas como parámetros
• Descripción
o Paso de una función como parámetro de otra función f
1. Función definida previamente
(define (h …)
<cuerpo de h>
87
<cuerpo de h>
)
…
(f pr1 pr2 … pri h pri+1 … prn)
donde pr1, pr2, …, pri, h, pri+1, …, prn
son los parámetros reales de f
![Page 88: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/88.jpg)
3. Funciones pasadas como parámetros
• Descripción
o Paso de una función como parámetro de otra función f
2. Función creada con lambda
(f pr pr … pr
88
(f pr1 pr2 … pri
(lambda (<parámetros) <cuerpo>)
pri+1 … prn
)
![Page 89: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/89.jpg)
3. Funciones pasadas como parámetros
• Descripción
• Ejemplos
• Aplicaciones
89
![Page 90: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/90.jpg)
3. Funciones pasadas como parámetros
• Ejemplos
o Función que recibe otra función como parámetro
(define (duplicar g x)
(* 2 (g x))
)
90
Uso de la función Función pasada como parámetro
![Page 91: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/91.jpg)
3. Funciones pasadas como parámetros
• Ejemplos
o Función que recibe otra función como parámetro
1. Función definida previamente
(define (duplicar g x)
(* 2 (g x))
91
)
(define (cuadrado x)
(* x x)
)
(duplicar cuadrado 7)� 98
Función pasada como parámetro
![Page 92: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/92.jpg)
3. Funciones pasadas como parámetros
• Ejemplos
o Función que recibe otra función como parámetro
2. Función creada con lambda (1/2)
(define (duplicar g x)
(* 2 (g x))
92
)
(duplicar (lambda (x) (* x x)) 7)� 98
Función lambda pasada como parámetro
![Page 93: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/93.jpg)
3. Funciones pasadas como parámetros
• Ejemplos
o Función que recibe otra función como parámetro
2. Función creada con lambda (2/2)
(define (duplicar g x)
(* 2 (g x))
93
)
(duplicar (lambda (x) (+ x 1)) 7)� 16
Función lambda pasada como parámetro
![Page 94: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/94.jpg)
3. Funciones pasadas como parámetros
• Descripción
• Ejemplos
• Aplicaciones
• Series numéricas
• Raíz de una función mediante bisección
94
![Page 95: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/95.jpg)
3. Funciones pasadas como parámetros
• Descripción
• Ejemplos
• Aplicaciones
• Series numéricas
• Raíz de una función mediante bisección
95
![Page 96: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/96.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Ejemplos preparatorios
� Suma de cubos
� Suma de pi-octavos
o Estructura general de los ejemplos preparatorios
96
o Estructura general de los ejemplos preparatorios
o Función que suma cualquier serie numérica
� Series no paramétricas
� Series paramétricas
![Page 97: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/97.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Ejemplos preparatorios: suma de cubos
(define (suma-cubos inicial final);; función auxiliar
(define (cubo x) (* x x x))
333333 )1(...)2()1( bbaaan
b
an
+−++++++=∑=
97
(define (cubo x) (* x x x));; cuerpo de suma-cubos(if (> inicial final)
0(+
(cubo inicial)(suma-cubos (+ inicial 1) final)
))
)
![Page 98: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/98.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Ejemplos preparatorios: suma de cubos
(define (suma-cubos inicial final);; función auxiliar
(define (cubo x) (* x x x))
333333 )1(...)2()1( bbaaan
b
an
+−++++++=∑=
98
(define (cubo x) (* x x x));; cuerpo de suma-cubos(if (> inicial final)
0(+
(cubo inicial)(suma-cubos (+ inicial 1) final)
))
)
Término de la serie
Siguiente elemento de la serie
![Page 99: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/99.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Ejemplos preparatorios: pi octavos
(define (suma-pi-octavos inicial final)(define (termino n)
. . . )2(
1
4
1 8
π+
11 9
1 +
7 5
1 +
3 1
1 =
×××=
+×∑
∞
+=
=
nn
n nn
99
(define (termino n)(/ 1.0 (* n (+ n 2.0)))
)(if (> inicial final)
0(+
(termino inicial)(suma-pi-octavos (+ inicial 4.0) final)
))
)
![Page 100: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/100.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Ejemplos preparatorios: pi octavos
(define (suma-pi-octavos inicial final)(define (termino n)
. . . )2(
1
4
1 8
π+
11 9
1 +
7 5
1 +
3 1
1 =
×××=
+×∑
∞
+=
=
nn
n nn
100
(define (termino n)(/ 1.0 (* n (+ n 2.0)))
)(if (> inicial final)
0(+
(termino inicial)(suma-pi-octavos (+ inicial 4.0) final)
))
)
Término de la serie
Siguiente elemento de la serie
![Page 101: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/101.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Estructura general de los ejemplos preparatorios
(define (<nombre> inicial final)(if (> inicial final)
0(+
101
(+ (<término> inicial)(<nombre> (<siguiente> inicial) final)
))
)
o Observación� Las funciones término y siguiente son externas
![Page 102: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/102.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica
donde
t(n)seriefinal
s(n)nn
inicialn
∑+=
=
=
102
donde
� t: término general de la serie
� s: siguiente elemento
s(n)nn +=
![Page 103: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/103.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión recursiva
t(n)seriefinal
s(n)nn
inicialn
∑+=
=
=
103
(define (sumar-serie término siguiente inicial final)(if (> inicial final)
0(+
(término inicial)(sumar-serie término siguiente (siguiente inicial) final)
))
)
s(n)nn +=
![Page 104: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/104.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión recursiva
(define (sumar-serie término siguiente inicial final)
Paso de las funciones como parámetros
104
(define (sumar-serie término siguiente inicial final)(if (> inicial final)
0(+
(término inicial)(sumar-serie término siguiente (siguiente inicial) final)
))
)
Uso de la función
Paso de las funciones como parámetros
![Page 105: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/105.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión recursiva. Ejemplo 1/7
333333 )1(...)2()1( bbaaan
b
an
+−++++++=∑=
105
;; función que calcula el término de la serie (define (cubo x) (* x x x))
;; función para obtener el “siguiente” elemento(define (suma-uno x) (+ x 1.0))
;; llamada a sumar-serie(sumar-serie cubo suma-uno 1 3)� 36.0
![Page 106: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/106.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión recursiva. Ejemplo 2/7
;; llamada a sumar-serie usando funciones anónimas
333333 )1(...)2()1( bbaaan
b
an
+−++++++=∑=
106
;; llamada a sumar-serie usando funciones anónimas
(sumar-serie(lambda (x) (* x x x))(lambda (x) (+ x 1))1 3
)� 36.0
![Page 107: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/107.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión recursiva. Ejemplo 3/7
;; función que calcula el término de la serie
8119
1
75
1
31
1
2
1
4
1
π + . . .
+
+
)(nnnn
n
=×××
=+×
∑∞
+=
=
107
;; función que calcula el término de la serie(define (termino-pi x)
(/ 1.0 (* x (+ x 2.0))))
;; función para obtener el “siguiente” elemento(define (siguiente-pi x) (+ x 4))
;;llamada a la función sumar-serie(* 8.0 (sumar-serie termino-pi siguiente-pi 1 10000)
� 3.14139265
![Page 108: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/108.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión recursiva. Ejemplo 4/7
;; función que calcula el término de la serie
69
1
4
1
1
1
3
1
2
1
1
112
2221
2
π......
nn
=+++=+++=∑∞
=
108
;; función que calcula el término de la serie(define (termino n)
(/ 1.0 (* n n)))
;; función para obtener el “siguiente” elemento(define (siguiente n) (+ n 1))
;; llamada a la función sumar-serie(sumar-serie termino siguiente 1 1000)� 1.6439…
![Page 109: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/109.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión recursiva. Ejemplo 5/7
;; función que calcula el término de la serie
.182847182826
1
2
1
1
1
3
1
2
1
1
11
1
.. ,e......!!!
n!
n
==+++=+++=∑∞
=
109
;; función que calcula el término de la serie(define (termino n)
(/ 1.0 (factorial n)))
;; función para obtener el “siguiente” elemento(define (siguiente n ) (+ n 1))
;; llamada a la función sumar-serie(sumar-serie termino siguiente 1 10)� 2.7182818284…
![Page 110: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/110.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión recursiva
� Ejemplo 6/7: integral definida
110o “h” debe ser suficientemente pequeño
a b a+h/2+ h a+h/2 a+h/2+2h
…
( ) h . h) + . . + /h)+ f(a+h )+ f(a+h/ f(a+h/ f(x) b
a×+=∫ 2222
![Page 111: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/111.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricaso Función que suma cualquier serie numérica no
paramétrica: versión recursiva� Ejemplo 7/7: integral definida
(define (integral f inicial final h);; función para obtener el siguiente elemento(define (sumar-h x) (+ x h))
111
(define (sumar-h x) (+ x h));; cuerpo de integral
(*(sumar-serie f sumar-h (+ inicial (/ h 2)) final)h
))
(define (f x) x)(integral f 0 1 0.001) � 0.50000000(integral (lambda (x) x) 0 1 0.001) � 0.50000000
![Page 112: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/112.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión iterativa
(define (sumar-serie-v2 termino siguiente inicial final)(do
(
112
((i inicial (siguiente i))(resultado 0 (+ resultado (termino i))))
;;((> i final) resultado);; No hay cuerpo)
)
![Page 113: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/113.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica noparamétrica: versión iterativa. Ejemplo.
333333 121 b)(b...)(a)(aan
b
an
+−++++++=∑=
113
;; función que calcula el término de la serie(define (cubo x) (* x x x))
;; función para obtener el “siguiente” elemento(define (siguiente n) (+ n 1))
;; llamada a la función(sumar-serie-v2 cubo siguiente 1 3) � 36.0
![Page 114: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/114.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica paramétrica
t(x,n)serie(x)final
inicialn
∑=
=
114
donde
� x: parámetro
� t: término general de la serie
� s: siguiente elemento
s(n)nn
inicialn
+=
=
![Page 115: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/115.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica paramétrica: versión recursiva
(define (sumar-serie-paramétrica término siguiente inicial final x)(if (> inicial final)
0(+
parámetro
115
(+(término x inicial )(sumar-serie-paramétrica
término siguiente (siguiente inicial) final x ))
))
![Page 116: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/116.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica paramétrica: versión iterativa
(define (sumar-serie-paramétrica término siguiente inicial final x)(do
((i inicial (siguiente i))
116
(i inicial (siguiente i))(resultado 0.0 (+ resultado (término x i))))
;;((> i final) resultado);; No hay cuerpo)
)
parámetro
![Page 117: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/117.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica paramétrica: versión iterativa. Ejemplo.
;; término de la serie(define (término-seno x n)
(* (expt -1 n)(/
n
nn
)!n(
x)(- seno(x) ∑
∞
=
+
+=
0
12
121
117
(/(expt x (+ (* 2 n) 1))(factorial (+ (* 2 n) 1))
))
);; función para obtener el “siguiente” elemento(define (incrementar-uno n)
(+ n 1))
![Page 118: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/118.jpg)
3. Funciones pasadas como parámetros
• Aplicación: series numéricas
o Función que suma cualquier serie numérica paramétrica: versión iterativa. Ejemplo.
(sumar-serie-paramétrica
n
nn
)!n(
x)(- seno(x) ∑
∞
=
+
+=
0
12
121
118
(sumar-serie-paramétrica término-seno incrementar-uno 0 100 (/ pi 2.0)
)� 1.0000000000000002
![Page 119: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/119.jpg)
3. Funciones pasadas como parámetros
• Descripción
• Ejemplos
• Aplicación
• Series numéricas
• Raíz de una función mediante bisección
119
![Page 120: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/120.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
f(b)
120
f(a)
x0
![Page 121: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/121.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
f(b)
121
f(a)
x1
x0
![Page 122: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/122.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
f(b)
122
f(a)
x1
X2 x0
![Page 123: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/123.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
o Restricción
� f(a) y f(b) deben tener signos diferentes
f(a) * f(b) < 0
� Por ejemplo:
123
� Por ejemplo:
� f(a) < 0
� f(b) > 0
![Page 124: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/124.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
o Funciones auxiliares
(define (cercanos? x y)(< (abs (- x y)) 0.001)
)
(define (promedio x y)
124
(define (promedio x y)(/ (+ x y) 2.0)
)
![Page 125: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/125.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
o Funciones auxiliares
(define (cercanos? x y)(< (abs (- x y)) 0.001)
)
(define (promedio x y)
125
(define (promedio x y)(/ (+ x y) 2.0)
)Se puede parametrizar
![Page 126: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/126.jpg)
• Aplicación: raíz de una función mediante bisección
(define (buscar f negativo positivo)(define (cercanos? x y)
(< (abs (- x y)) 0.001) )(define (promedio x y)
(/ (+ x y) 2.0) );; cuerpo de buscar(let ;; Variable local
((mitad (promedio negativo positivo)));; Cuerpo de let(if (cercanos? negativo positivo)
mitad
126
mitad(let ;; variable local
((valor (f mitad)));; cuerpo del let anidado(cond
((positive? valor) (buscar f negativo mitad))((negative? valor) (buscar f mitad positivo))(else mitad)
) )
))
)
![Page 127: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/127.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
o Llamada la función “buscar”
(define (f x)
(- (* x x) 2)
)
127
(buscar f 1 3) � 1.41455078
;; Modo alternativo
(buscar (lambda (x) (- (* x x) 2)) 1 3)
� 1.41455078
![Page 128: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/128.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
o Se va a definir una nueva función denominada bisección para controlar el signo de f(a) y f(b)
128
![Page 129: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/129.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
(define (bisección f a b)
(let ( (valor-a (f a))(valor-b (f b))
)(cond
129
(cond( (and (negative? valor-a) (positive? valor-b))(buscar f a b))
( (and (negative? valor-b) (positive? valor-a) )(buscar f b a))
(else (display “los puntos iniciales tienen el mismo signo”)))
)
)
![Page 130: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/130.jpg)
3. Funciones pasadas como parámetros
• Aplicación: raíz de una función mediante bisección
;; Ejemplo de llamada a la función bisección
(bisección sin 2 4) � 3.14111328
130
![Page 131: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/131.jpg)
Índice
1. Forma especial iterativa “do”
2. Recursión
Programación Declarativa Tema 4.- Recursión e iteración
131
3. Funciones pasadas como parámetros
4. Funciones devueltas como resultados
![Page 132: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/132.jpg)
4. Funciones devueltas como resultados
• Descripción
• Ejemplos
• Aplicación: método de Newton
132
![Page 133: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/133.jpg)
4. Funciones devueltas como resultados
• Descripción
• Ejemplos
• Aplicación: método de Newton
133
![Page 134: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/134.jpg)
4. Funciones devueltas como resultados
• Descripción
o Se puede devolver una función como resultado de otra función de dos maneras
1. Devolviendo el nombre de una función u operador
2. Devolviendo una función creada con lambda
134
2. Devolviendo una función creada con lambda
![Page 135: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/135.jpg)
4. Funciones devueltas como resultados
• Descripción
• Ejemplos
• Aplicación: método de Newton
135
![Page 136: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/136.jpg)
4. Funciones devueltas como resultados
• Ejemplo
1. Devolviendo el nombre de una función u operador
(define (elegir opcion f g)(if (even? opcion)
fg
136
g)
)
![Page 137: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/137.jpg)
4. Funciones devueltas como resultados
• Ejemplo
1. Devolviendo el nombre de una función u operador
;; Ejemplos de llamadas a la función devuelta
((elegir 1 abs sqrt ) 9) � 3
137
((elegir 2 * + ) 3 4 ) � 12
((elegir 2 (lambda (x) (+ x 1))(lambda (x) (* 2 x))
)9
) �10
![Page 138: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/138.jpg)
4. Funciones devueltas como resultados
• Ejemplo
2. Devolviendo una función creada con lambda
(define (componer f g)
(lambda (x)
(f (g x))
138
)
)
;; Llamada a la función devuelta
( (componer sqrt sqrt) 81) � 3
![Page 139: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/139.jpg)
4. Funciones devueltas como resultados
• Descripción
• Ejemplos
• Aplicación: método de Newton
139
![Page 140: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/140.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
Y = f(X)
140
![Page 141: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/141.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
Y = f(X)
141
x0
Se elige un punto inicial
![Page 142: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/142.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
Se traza la recta tangente: Y = f(x0) + f’(x0) × (X-x0)
Y = f(X)
142
x0
![Page 143: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/143.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
Se traza la recta tangente: Y = f(x0) + f’(x0) × (X-x0)
Y = f(X)
143
x0x1
Se obtiene el punto de corte con el eje de abscisas
![Page 144: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/144.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o Sea x0 una aproximación inicial a la raíz de la función
o Si f(x0) ≠ 0 entonces se obtiene el siguienteelemento de la sucesión en la intersección de
144
� Eje de abscisas: Y = 0
� Recta tangente a la curva y = f(x) en el punto (x0, f(x0))
Y = f(x0) + f'(x0) (x - x0)
o El siguiente elemento es )('
)(
0
0
01
xx
xxf
f−=
![Page 145: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/145.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o En general, el término general de la sucesión es
)xnf( −=
145
)xnf '(
)xnf( x x nn
−=+1
![Page 146: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/146.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o En general, el término general de la sucesión es
)xnf( −=
146
o ¿Cuándo no se puede aplicar el método de Newton?
)xnf '(
)xnf( x x nn
−=+1
![Page 147: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/147.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o Aplicación a la función y = f(x) = x2 – a
cuya raíz es
Se obtiene la siguiente sucesión:
ay =
147
2
x
ax
2x
a x x)xf '(
)xf( xx
n
n
n
2
n
n
n
n
n1n
+
=−
−=−=+
![Page 148: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/148.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o Funciones auxiliares:
� Aproximación a la derivada de una función
h
xfhxfxDfxf
)()(lim)()('
−+==
148
� Cociente incremental
hxDfxf
hlim)()('
0
==→
f x h f x
h
( ) ( )+ −
![Page 149: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/149.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o Funciones auxiliares:
� Aproximación a la derivada de una función
(define (cociente-incremental f h)
149
(define (cociente-incremental f h)(lambda (x)
(/ (- (f (+ x h)) (f x))h
))
)
![Page 150: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/150.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o Funciones auxiliares:
� Aproximación a la derivada de una función
(define (cubo x) (* x x x))
150
(define (cubo x) (* x x x))
((cociente-incremental cubo 0.001) 5) � 75.01500100
o
((cociente-incremental (lambda (x) (* x x x)) 0.001) 5)� 75.01500100
![Page 151: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/151.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o Funciones auxiliares:
� Función para comprobar si la aproximación a la raíz es buena
151
(define (bueno? x f) (< (abs (f x)) 0.001))
Se puede parametrizar
![Page 152: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/152.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
o Funciones auxiliares:
� Función que obtiene el siguiente elemento de la sucesión
Se puede parametrizar
152
(define (siguiente x f)(- x
(/ (f x)((cociente-incremental f 0.001) x))
))
Se puede parametrizar
![Page 153: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/153.jpg)
4. Funciones devueltas como resultados
• Aplicación: método de Newton para calcular la raízde cualquier función
(define (newton f inicial)(if (bueno? inicial f)
inicial(newton f (siguiente inicial f))
)
153
))
(newton (lambda (x) (- (* x x) 2)) 1) � 1.41421657
![Page 154: INGENIERÍA INFORMÁTICA CUARTO CURSO PRIMER … · 2019-07-18 · Tema3.-Predicadosy sentenciascondicionales Tema4.-Iteracióny Recursión Tema5.-Tiposde DatosCompuestos Tema 6.-Abstracción](https://reader033.vdocumento.com/reader033/viewer/2022050108/5f4624cf9d4feb7f0828d038/html5/thumbnails/154.jpg)
UNIVERSIDAD DE CÓRDOBA
ESCUELA POLITÉCNICA SUPERIOR DE CÓRDOBA
DEPARTAMENTO DEINFORMÁTICA Y ANÁLISIS NUMÉRICO
PROGRAMACIÓN DECLARATIVAPROGRAMACIÓN DECLARATIVAPROGRAMACIÓN DECLARATIVAPROGRAMACIÓN DECLARATIVAINGENIERÍA INFORMÁTICA
CUARTO CURSO
PRIMER CUATRIMESTRE
Tema 4.- Recursión e iteración