Recursi´ on e iteraci´ on Se exponen en este apartado diversos ejemplos simples de definiciones de procedimientos que generan procesos recursivos o iterativos. Se comienza precisando algoritmos y sus correspondientes procedimientos para el c´alculo de potencias de exponente entero no negativo, primero en el monoide multiplicativo de los enteros y, posteriormente, potencias en un monoide cualquiera. Mediante estos ejemplos sencillos se ilustran definiciones de procedimientos recursivos e iterativos, as´ı como sus correspondientes procesos recursivos e iterativos. Tambi´en se ponen de manifiesto hechos cruciales relativos al consumo de tiempo y de memoria en los procesos computacionales.

[1] Comencemos considerando el concepto de potencia de exponente entero no negativo (se tomar´a, por simplificar, el monoide multiplicativo (Z, ×) de los enteros como dominio base). Deber´a tenerse en cuenta que no van a servir, en principio, definiciones “para andar por casa” al estilo de bn = b × b × . . . × b ; en lugar de este tipo de definiciones deberemos acudir al concepto matem´aticamente correcto de potencia. Fijado un n´ umero entero b, sea pb : N → Z la funci´ on tal que pb (0) = 1, pb (n + 1) = b × pb (n), (n ∈ N)

(1)

Se escribe bn = pb (n), para todo entero b y todo n´ umero natural n, y se dice que bn es la potencia de base b y exponente n; queda as´ı definida una aplicaci´ on p:Z×N→Z p(b, n) = bn , (b ∈ Z, n ∈ N) que, de acuerdo con (1), verifica: b0 bn

= 1 = b × bn−1

(b ∈ Z, n ∈ N, n > 0)

(1 )

Esta definici´ on matem´atica, recursiva, proporciona el procedimiento computacional

Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

1

(define (potencia base exponente) (if (zero? exponente) 1 (* base (potencia base (− exponente 1)))))

(2)

Ejemplo de uso: > (potencia 3 5) 243

El proceso generado en el c´alculo de (potencia 3 5) se puede esquematizar en la forma: (potencia 3 5) (* 3 (potencia 3 4)) (* 3 (* 3 (potencia 3 3))) (* 3 (* 3 (* 3 (potencia 3 2)))) (* 3 (* 3 (* 3 (* 3 (potencia 3 1))))) (* 3 (* 3 (* 3 (* 3 (* 3 (potencia 3 0)))))) (* 3 (* 3 (* 3 (* 3 (* 3 1))))) (* 3 (* 3 (* 3 (* 3 3)))) (* 3 (* 3 (* 3 9))) (* 3 (* 3 27)) (* 3 81) 243 El procedimiento potencia genera procesos recursivos que requieren un n´ umero de pasos (tiempo de ejecuci´on) que crece de modo lineal en la talla del exponente y usan memoria tambi´en lineal en la talla del exponente. ¿Es posible mejorar estas cotas? [2] Atendamos, en primer lugar, al tiempo de ejecuci´ on. De la definici´ on (1) se derivan propiedades de las potencias que pueden ayudar a disminuir el n´ umero de pasos; por ejemplo bn+m = bn × bm , de donde, si se toma m = n,

2

b2×n = bn × bn = (bn )

Por tanto, el c´ alculo de b2×n requiere exactamente una multiplicaci´ on m´as que el c´alculo n de b . De ah´ı que, si e > 0 es par, entonces be = (be/2 )2

(3)

El c´ alculo directo de be seg´ un (1) conlleva una multiplicaci´ on m´ as que el c´alculo de be−1 , mientras que usando (3) el n´ umero de multiplicaciones requeridas es una m´ as que el c´alculo de be/2 . Ahora, si e/2 es par se vuelve a usar (3); mientras que si e/2 es impar, se procede como en (1): e be/2 = b × b( 2 −1) Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

2

y

e 2

− 1 es par, con lo que se le puede aplicar nuevamente la reducci´ on (3), etc.

Estas consideraciones conducen a la formulaci´ on siguiente: Dado un entero b, para todo entero no negativo n se tiene b0 bn bn

= 1 = (bn/2 )2 , si n > 0 y n es par = b × bn−1 , si n > 0 y n es impar

(4)

que en t´erminos de procedimientos se expresa (define (pot base exponente) (cond ((zero? exponente) 1) ((even? exponente) (cuadrado (pot base (/ exponente 2)))) (else (* base (pot base (− exponente 1))))))

(5)

(define (cuadrado x) (* x x))

Ejemplo de uso: > (pot 2 21) 2097152

El proceso generado en el c´alculo de (pot 2 21) se puede esquematizar en la forma: (pot 2 21) (* 2 (pot 2 20)) (* 2 (cuadrado (pot 2 10))) (* 2 (cuadrado (cuadrado (pot (* 2 (cuadrado (cuadrado (* 2 (* 2 (cuadrado (cuadrado (* 2 (* 2 (cuadrado (cuadrado (* 2 (* 2 (cuadrado (cuadrado (* 2 (* 2 (cuadrado (cuadrado (* 2 (* 2 (cuadrado (cuadrado (* 2 (* 2 (cuadrado (cuadrado (* 2 (* 2 (cuadrado 1024)) (* 2 1048576) 2097152

2 5)))) (pot 2 4))))) (cuadrado (pot 2 2)))))) (cuadrado (cuadrado (pot 2 1))))))) (cuadrado (cuadrado (* 2 (pot 2 0)))))))) (cuadrado (cuadrado (* 2 1))))))) (cuadrado 4))))) 16))))

El procedimiento pot genera procesos recursivos que requieren un n´ umero de pasos que crece logar´ıtmicamente con el exponente. El paso de un tiempo lineal a un tiempo logar´ıtmico es crucial: el c´alculo de b elevado a 1048576 (= 220 ) requerir´ıa 1048575 multiplicaciones seg´ un el procedimiento potencia y solamente 20 = log2 (1048576) multiplicaciones seg´ un el procedimiento pot . Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

3

[3] Expongamos ahora otro punto de vista, radicalmente distinto al anterior, para el c´ alculo de potencias de acuerdo con el siguiente esquema adaptado al caso concreto 35 ; se comienza con una variable a con valor inicial 1, una variable b con valor la base (3 en nuestro caso) y una variable n con valor inicial el exponente (5 en nuestro caso), de modo repetitivo se multiplica a por la base b a la vez que se disminuye n en una unidad: a

b

n

1

3

5

1×3 =

3

3

4

3×3 =

9

3

3

9×3 =

27

3

2

27×3 =

81

3

1

81×3 =

243

3

0

cuando n alcance 0, el valor de a es la potencia buscada. Formalicemos esta forma de proceder. Dado un n´ umero entero b, consideremos la funci´ on Pb : Z × N → Z tal que Pb (a, 0) = a, Pb (a, n + 1) = Pb (a × b, n),

para todo a ∈ Z para todo a ∈ Z, n ∈ N

(6)

Se tiene Pb (a, n) = a × bn 

(7)

Demostraci´ on: Por inducci´ on sobre n. Pb (a, 0) = a = a × b0 , y Pb (a, n + 1) = Pb (a × b, n) = (a × b) × bn = a × bn+1



En particular, para a = 1: Pb (1, n) = bn

(8)

Queda definida una funci´ on P

: Z×Z×N (a, b, n)

→  →

Z Pb (a, n)

y se cumple P (a, b, n) = a × bn . Teniendo en cuenta (6), la funci´ on P se expresa en la forma P (a, b, 0) = a P (a, b, n) = P (a × b, b, n − 1)

(a, b ∈ Z, n ∈ N, n > 0)

Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

(9) 4

y se tiene bn = P (1, b, n)

(10)

Pasemos a definir los correspondientes procedimientos computacionales. La funci´ on P se implementa, teniendo en cuenta (9), como el procedimiento pot2Iter: (define (pot2Iter a b n) (if (zero? n) a (pot2Iter (* a b) b (− n 1))))

(11)

y de (10) se obtiene (12)

(define (pot2 base exponente) (pot2Iter 1 base exponente))

Ejemplo de uso: > (pot2 3 5) 243

El proceso generado en la evaluaci´ on de (pot2 3 5) es como sigue: (pot2 3 5) llama a pot2Iter con los par´ ametros a, b, n reemplazados por 1, 3, 5, respectivamente. Posteriormente, y de modo repetitivo (i.e. iterativo), se eval´ uan a * b, b y n − 1, despu´es estos valores pasan a ser (en paralelo) los nuevos valores de a, b y n, respectivamente: (a, b, n) ← (a * b, b, n − 1) hasta que el valor de n sea 0 en cuyo momento se para el proceso y devuelve 243 como valor de (pot2Iter 1 3 5); esto es, como valor de (pot2 3 5). El siguiente esquema puede ayudar a entender el proceso:

Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

5

(pot2 3 5) = . (pot2Iter 1 3 5) = . . (pot2Iter 3 3 4) = . . . (pot2Iter 9 3 3) = . . . . (pot2Iter 27 3 2) = . . . . . (pot2Iter 81 3 1) = . . . . . . (pot2Iter 243 3 0) = . . . . . . 243 = . . . . . 243 = . . . . 243 = . . . 243 = . . 243 = . 243 = 243

Los procedimientos potencia y pot2 calculan potencias de exponente natural de n´ umeros enteros, pero son esencialmente distintos en cuanto a la forma de calcularlos o, con mayor precisi´ on, los procesos generados son diferentes: – La definici´ on de potencia es recursiva en el sentido de que potencia se llama a s´ı mismo [en la definici´ on (2)], y el proceso generado por (potencia b n) es estrictamente recursivo en el sentido de que en cada paso queda aplazada una evaluaci´ on [el producto (* base (potencia base (− exponente 1))) ] – La definici´ on de pot2Iter es recursiva, pot2Iter se llama a s´ı mismo [en la definici´ on (11)], pero el proceso generado por (pot2Iter a b n) es esencialmente iterativo en el sentido de que la respuesta se va construyendo mientras el proceso avanza y no quedan (o no deber´ıan quedar) evaluaciones aplazadas. Una de las ventajas de esta forma recursivo-iterativa de pensar es que el par de definiciones (11), (12) se traduce autom´ aticamente a una definici´ on de procedimiento que generar´ a procesos puramente iterativa; esto se consigue mediante el uso de alguna de las primitivas de iteraci´ on expl´ıcita que proporcione el lenguaje o el sistema, por ejemplo, do en Scheme. Veamos c´omo llevar a cabo esta traducci´ on autom´ atica mediante una sucesi´on de pasos seg´ un se expone seguidamente: 1. la entrada (los datos) es un par (base, exponente) ∈ Z × N (primera l´ınea del procedimiento (12)). 2. se invoca pot2Iter con sus par´ ametros a, b, n inicializados como 1, base, exponente, respectivamente (segunda l´ınea de (12)). 3. cuando n alcance el valor 0 se devuelve el valor de a (segunda l´ınea de (11)). Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

6

4. si n no es 0 se efect´ ua el cambio (a, b, n) ← (a * b, b, n − 1) y se repite la evaluaci´ on de pot2Iter con estos nuevos valores (tercera l´ınea de (11)). Estamos en condiciones de definir un procedimiento que genere procesos puramente iterativo para el c´ alculo de potencias seg´ un el esquema indicado: (define (pot3 base exponente) (do ((a 1 (* a b)) (b base) (n exponente (− n 1))) ((zero? n) a))) [4] Combinemos ahora dos puntos de vista tratados previamente: – proceso iterativo del apartado anterior [3] y – tiempo logar´ıtmico del apartado [2]. Para ello debemos tener en cuenta que si n es par, entonces bn = (bn/2 )2 = (b2 )n/2 Volvamos a usar las funciones Pb y P del apartado [3]. En la situaci´ on all´ı contemplada, y si n es un entero positivo par, se tiene: P (a, b, n) = Pb (a, n) = a × bn = a × (b2 )n/2 = Pb2 (a, n/2) = P (a, b2 , n/2) Por lo tanto las expresiones de (9) se escriben P (a, b, 0) = a P (a, b, n) = P (a, b2 , n/2), si n es par P (a, b, n) = P (a × b, b, n − 1), si n es impar

(a, b ∈ Z, n ∈ N, n > 0)

(13)

y se tiene, v´ease (10), bn = P (1, b, n) Esto proporciona la siguiente definici´ on de procedimiento: (define (pot4Iter a b n) (cond ((zero? n) a) ((even? n) (pot4Iter a (* b b) (/ n 2))) (else (pot4Iter (* a b) b (− n 1))))) (define (pot4 base exponente) (pot4Iter 1 base exponente)) Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

7

Ejemplo de uso: > (pot4 5 87) 6462348535570528709932880406796584793482907116413116455078125

El procedimiento pot4 iter (recursivo-iterativo) genera procesos (que deber´ıan ser) iterativos con un n´ umero de pasos que crece logar´ıtmicamente con el tama˜ no de exponente. Ahora, y como traducci´ on directa del procedimiento anterior, veamos la versi´ on puramente iterativa: (define (pot5 base exponente) (do ((a 1 (if (even? (b base (if (even? (n exponente (if (even? ((zero? n) a)))

n) a (* a b))) n) (* b b) b)) n) (/ n 2) (− n 1))))

Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

8

[5] Generalizaci´on mediante procedimientos de orden superior. La definici´ on de potencia de exponente natural en el dominio Z de los enteros, vista en (1), se generaliza de modo obvio al caso de un monoide arbitrario M = (M, •). Recordemos que • es una operaci´ on binaria en M asociativa y con elemento unidad (necesariamente u ´nico), digamos e. La definici´ on (1) se expresa ahora: Fijado un elemento b ∈ M , sea pb : M → M la funci´ on tal que pb (0) = e, pb (n + 1) = b • pb (n), (n ∈ N)

(14)

El resto de la discusi´ on es igual con los cambios: la unidad: 1 por e y la operaci´ on: × por • ; en particular, las relaciones (13) se escriben: P (a, b, 0) P (a, b, n) P (a, b, n)

= a = P (a, b • b, n/2), si n es par = P (a • b, b, n − 1), si n es impar

(a, b ∈ M, n ∈ N, n > 0)

(15)

y se tiene pb (n) = P (e, b, n),

(b ∈ M, n ∈ N)

Para implementar (15) es preciso incluir, adem´ as de la base y el exponente, la operaci´ on binaria • (como un procedimiento de dos argumentos) y la unidad e. Por lo dem´as el procedimiento Potencia es una copia casi exacta del procedimiento pot5 de la secci´on previa: (define (potenciaGeneral base exponente operador unidad) (do ((a unidad (if (even? n) a (operador a b))) (b base (if (even? n) (operador b b) b)) (n exponente (if (even? n) (/ n 2) (− n 1)))) ((zero? n) a)))

Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

9

Ejemplos de uso: 1 En el monoide multiplicativo de los enteros: > (potenciaGeneral 5 7 * 1) 78125

> (expt 5 7) 78125

2 En el monoide aditivo de los enteros (aqu´ı se dice m´ ultiplo en lugar de potencia): > (potenciaGeneral 123 9876 + 0) 1214748

> (* 123 9876) 1214748

3 En el monoide multiplicativo de los enteros modulo 37. La operaci´ on es multiplicaci´ on ordinaria de enteros seguida de reducci´ on con respecto al m´odulo, 37 en este caso: > (potenciaGeneral 22 13 (lambda (u v) (remainder (* u v) mod) 1) 17

(define (potenciaModular base exponente mod) (potenciaGeneral base exponente (lambda (u v) (remainder (* u v) mod)) 1)) > (potenciaModular 234 567 890) 594

> (potenciaModular −234 567 890) -594

Obs´ervese que en el u ´ltimo ejemplo, utilizando nuestra funci´ on Potencia, se obtiene un resultado correcto pero negativo: (−234)567 ≡ −594(mod 890) Esta aparente anomal´ıa se debe al funcionamiento de la primitiva remainder de Scheme: Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

10

> (remainder 7 5) 2

> (remainder 7 −5) 2

> (remainder −7 5) -2

> (remainder −7 −5) -2

Como puede verse remainder devuelve el resto con el signo del dividendo. Si se quiere que los restos sean no negativos, definamos un procedimiento resto que devuelva restos no negativos: (define (resto a b) (let ((r (remainder a b))) (if (>= r 0) r (+ (abs b) r)))) (define (potenciaModular base exponente mod) (potenciaGeneral base exponente (lambda (u v) (resto (* u v) mod)) 1)) Ejemplo de uso: (potenciaModular −22 13 37) 20

Teorema de Fermat. Si p es un entero primo y a es un entero, 0 ≤ a < p, entonces ap ≡ a (mod p) Por tanto, dado un entero n, n > 1, si para cualquier entero a, 1 < a < n, ocurre que an ≡ a (mod n) entoces n es compuesto. Ejercicio. Compru´ebese que 87669562583239363359710599 es compuesto.

Programaci´ on en Matem´ aticas. Carlos Ruiz de Velasco y Bellas, Universidad de Cantabria, Santander. 10 de octubre de 2003

11