PDF de programación - Bloque 1. Conceptos y técnicas básicas en programación - 4. Iteración y recursión

Bloque 1. Conceptos y técnicas básicas
en programación
1. Introducción
2. Datos y expresiones. Especificación de algoritmos
3. Estructuras algorítmicas básicas
4. Iteración y recursión
5. Iteración y recursión sobre secuencias
6. Iteración y recursión sobre tablas

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN
4

© Michael González Harbour y José Luis Montaña

10/nov/09

1

Notas:

UNIVERSIDAD
DE CANTABRIA

1. Introducción

2. Datos y expresiones. Especificación de algoritmos

3. Estructuras algorítmicas básicas

4. Iteración y recursión

• Diseño iterativo. Instrucciones de bucle. Invariantes y cotas. Fases de un diseño iterativo. Ejemplos.

Recursión. Ejemplos. Corrección de la implementación recursiva. Fases del diseño recursivo.

5. Iteración y recursión sobre secuencias

6. Iteración y recursión sobre tablas

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

2

UNIVERSIDAD
DE CANTABRIA

Diseño iterativo
Se trata de indicar al computador cómo se calcula la función
especificada repitiendo muchas veces un conjunto de
instrucciones
La sintaxis de un algoritmo iterativo es:
mientras B hacer
S;
fmientras
• donde B es un predicado y S un conjunto de instrucciones
La estructura completa se llama bucle, B se llama condición de
continuación y S cuerpo del bucle

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

3

Ejemplo
Vamos a escribir un método para obtener el valor del logaritmo de
y=1+x de acuerdo con el siguiente desarrollo en serie

UNIVERSIDAD
DE CANTABRIA

ln

x+(
1

)

=

x

x2
----–
2

+

x3
----
3

x4
----–
4

+

…

+

1–(

)n

1– xn
----
n

,

1–

1≤<

x

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

4

Especificación
método logaritmo (real y, entero n) retorna real
{Pre: 0<y<=2, n>0}
desarrollo en serie
{Post: x=y-1, valor retornado =
fmétodo

n
∑
1=

1–(

xi
----
i

}

)i

1–

i

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

5

UNIVERSIDAD
DE CANTABRIA

Diseño
método logaritmo (real y, entero n) retorna real
{Pre: 0<y<=2, n>0}
var
real x:=y-1; real numerador:=x; real log:=0;
entero signo:=1; entero i:=1;
fvar
mientras i<=n hacer
log:=log+signo*numerador/i;
numerador:=numerador*x;
signo:=-signo;
i++;
fmientras
retorna log;
{Post: x=y-1, valor retornado =
fmétodo

n
∑
1=

1–(

xi
----
i

}

)i

1–

i

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

6

Traza de un proceso iterativo
Estado al comenzar el bucle, en cada una de sus sucesivas
iteraciones

UNIVERSIDAD
DE CANTABRIA

y
1.2
1.2
1.2
1.2

x
0.2
0.2
0.2
0.2

i
1
2
3
4

numerador

signo

0.2
0.04
0.008
0.0016

1
-1
1
-1

log
0

0.19999
0.17999
0.18266

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

7

UNIVERSIDAD
DE CANTABRIA

Invariantes
Es una descripción del estado de las variables al comenzar la
iteración
• se mantiene inalterada después de cada iteración
Invariante del ejemplo
• log contiene la suma de los términos de la serie hasta i-1
• i es el término que vamos a tratar, 1<=i<=n+1
• signo es -1i-1
• numerador es xi
Cuando nos salimos del bucle:
• i vale n+1, y log contiene la suma de la serie hasta i-1=n

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

8

Relación del invariante con la
estructura del bucle
inicializaciones;
{se cumple el Invariante I}
mientras B hacer
{se cumplen I y B}
S;
{se cumple I}
fmientras
{se cumple I y no B}
acciones finales;
{se cumple la Postcondición}

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

9

Fases de un diseño iterativo
• Diseñar el invariante

UNIVERSIDAD
DE CANTABRIA

- para que indique el resultado que se obtendrá a cada paso del

bucle

• Determinar las inicializaciones para que se cumpla el invariante
• Determinar la condición de continuación, que nos permite saber

cuándo abandonamos el bucle
• Determinar el cuerpo del bucle

- comprobar que se sigue cumpliendo el invariante cada vez

• Verificar que el bucle termina
• Razonar sobre el estado obtenido a la terminación y determinar

las acciones finales, para que se cumpla la postcondición

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

10

UNIVERSIDAD
DE CANTABRIA

Terminación del bucle
Para verificar que el bucle termina puede plantearse la función de
cota
• indica la "distancia" máxima hasta la finalización del bucle
• debe ir reduciéndose con cada iteración, hasta llegar a cero
En el ejemplo de la suma de una serie, la función de cota es el
número de iteraciones que faltan: n+1-i
• a medida que i avanza, la función de cota se reduce
• cuando i llega al valor n+1 la cota es cero y el bucle termina

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

11

Ejercicios propuestos
1. Calcular la potencia entera de un número real x: xn
2. Calcular el seno de un ángulo x usando el siguiente desarrollo
en serie:

UNIVERSIDAD
DE CANTABRIA

sin

x( )

=

x

x3
-----–
3!

+

x5
-----
5!

x7
-----–
7!

+

…

+

1–(

)n x2n
----------------------
2n
)!
(

1+
1+

,

x R∈

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

12

Sintaxis alternativas: bucle con
condición de permanencia al final
En ocasiones interesa evaluar la condición de permanencia al
finalizar el bucle
• cuando se requiere para su evaluación haber ejecutado las

UNIVERSIDAD
DE CANTABRIA

instrucciones del bucle

• sintaxis
hacer
instrucciones;
mientras condición;

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

13

UNIVERSIDAD
DE CANTABRIA

Sintaxis alternativas: bucle con
variable de control
En otras ocasiones hay bucles en que el número de veces en que
se hace el bucle se cuenta mediante una variable de control
• sintaxis:
para i=0 hasta i=100 hacer
instrucciones
fpara
O con un paso diferente a la unidad
• sintaxis:
para i=0 hasta i=100 paso 2 hacer
instrucciones
fpara

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

14

Ejemplo
Algoritmo iterativo para el cálculo del factorial de un número
natural

UNIVERSIDAD
DE CANTABRIA

n!
⋅

1=
⋅

n,
⋅

0=
1–(

n!

=

1 2 3 … n

⋅

) n
⋅

,

n

1≥

Especificación
método factorial (n:entero) retorna entero
{Pre: n>=0}
cálculo del factorial
{Post: valor retornado=n!}
fmétodo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

15

UNIVERSIDAD
DE CANTABRIA

Diseno iterativo del método factorial
Usaremos el bucle con variable de control
Invariante:
• i es el paso a realizar; su rango de valores es: 1<=i<=n+1
• f tiene el resultado hasta el paso i-1, f=(i-1)!,
Inicializaciones:
•i:=1
•f:=1
Cuerpo del bucle:
•f:=f*i
•i++;

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

16

UNIVERSIDAD
DE CANTABRIA

Estructura final
método factorial (n:entero) retorna entero
{Pre: n>=0}
var
entero f:=1; entero i:=1;
fvar
{Invariante I: f=(i-1)!, 1<=i<=n+1}
mientras i<=n hacer
{se cumple I e 1<=i<=n}
f:= f*i;
i++;
fmientras
{se cumple I e i=n+1}
retorna f;
{Post: valor retornado=n!}
fmétodo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

17

UNIVERSIDAD
DE CANTABRIA

Estructura final usando el bucle con
variable de control
método factorial (n:entero) retorna entero
{Pre: n>=0}
var
entero f:=1;
fvar
para i=1 hasta i=n hacer
{Invariante: f=(i-1)!, 1<=i<=n+1}
f:= f*i;
fpara
retorna f;
{Post: valor retornado=n!}
fmétodo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

18

UNIVERSIDAD
DE CANTABRIA

Recursión
Muchos algoritmos iterativos pueden resolverse también con un
algoritmo recursivo
• el algoritmo se invoca a sí mismo
• en ocasiones es más natural
• en otras ocasiones es más engorroso
El diseño recursivo consiste en diseñar el algoritmo mediante una
estructura alternativa de dos ramas
• caso directo: resuelve los casos sencillos
• caso recursivo: contiene alguna llamada al propio algoritmo

que estamos diseñando

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

19

Ejemplos
Definición iterativa para el cálculo del factorial de un número
natural

UNIVERSIDAD
DE CANTABRIA

n!
⋅

1=
⋅

n,
⋅

0=
1–(

n!

=

1 2 3 … n

⋅

) n
⋅

,

n

1≥

Definición recursiva para el cálculo del factorial de un número
natural

n!
=

n!

1=
n
⋅

n,
n
1–(

0=
)!
,

n

1≥

La definición es correcta pues el número de recursiones es finito

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

10/nov/09

20

UNIVERSIDAD
DE CANTABRIA

Ejemplo: Diseño del algoritmo
método factorial (n:entero) retorna entero
{Pre: n>=0}
si n<=1 entonces
// caso directo
reto