PDF de programación - recursion punto fijo

1. El significado de la recursión

La recursión (en particular la iteración) es una componente funda-
mental de los lenguajes de programación. Vamos aquí a mostrar cuales
son las dificultades que surgen al intentar dar significado a la misma.
Resulta instructivo comenzar analizando el problema de definir funcio-
nes recursivas enteras. Consideramos la siguiente definición en Haskell:

g :: Int ->Int
g n = if n == 0 then 0

else if n == 1 then 1

else g (n-2)

¿qué función define? Si quisiera darle significado a este programa, ¿cuál
sería la función f ∈ Z → Z que representa a g?

Intuitivamente, dicha f debería satisfacer una ecuación parecida a la

que define a g en Haskell:

 0

f n =

1
f (n − 2)

si n = 0
si n = 1
caso contrario (c.c.)

(ER)

Por nuestro background, instantáneamente leemos la definición de f
como si fuera una definición recursiva. Con esa intuición, enseguida
concluimos que se trata de la función módulo 2 para los n ≥ 0, y para
los negativos "no termina". Llamemos mod2 a dicha función:

(cid:40) n %2

si n ≥ 0
no termina si n < 0

mod2 n =

Pero en realidad, esa lectura que hicimos, y que nos permitió concluir
que f era en realidad una forma de definir mod2, es apresurada. Es
la que nos indica nuestra intuición, que proviene de los lenguajes de
programación donde estamos acostumbrados al uso de la recursión y
también de las funciones parciales. Pero no deberíamos olvidarnos de
que nuestro metalenguaje tiene solamente funciones totales y que, por
lo tanto, no podemos concluir tan fácilmente que nuestra intuición -
acostumbrada a un contexto de funciones parciales- nos dé trivialmente
la solución correcta.

Surgen varias dificultades al pretender dar significado de manera
genérica a las funciones definidas de esta manera. Primero debemos
observar que dominio semántico Z → Z es inadecuado, ya que al incluir
la recursión se incorpora la posibilidad de que la evaluación que efectúa
haskell no termine. Incorporaremos un objeto al dominio de “resultados
posibles” que puede tomar una función entera, que usualmente denota

1

2
la “no terminación”: ⊥, denominado bottom. La razón de la elección de
este símbolo quedará clara con el desarrollo de la teoría del punto fijo
como modelo matemático. De manera que nuestro nuevo ”espacio de
significado“ para una ecuación como la de arriba será Z → Z⊥, donde
Z⊥ = Z ∪ {⊥}.

Note que podemos ahora definir mod2 como función total:

(cid:40) n %2 si n ≥ 0

⊥

si n < 0

mod2 n =

Volviendo a las dificultades que surgen al intentar dar significado a
la recursión, la principal tiene que ver con que hay varias funciones de
Z → Z⊥ que satisfacen la ecuación (ER).

Veamos, por ejemplo, si mod2 satisface la ecuación (ER) que se dió
para definir f. Para ello, colocamos mod2 en lugar de f a ambos lados
de la ecuación:

mod2 n =

1
mod2 (n − 2)

si n = 0
si n = 1
si n (cid:54)∈ {0, 1}

¿Se satisface esta ecuación?
Para analizarla, analicemos ambos miembros de la ecuación por se-

parado:

 0

 0

izq = mod2 n

der =

1
mod2 (n − 2)

si n = 0
si n = 1
si n (cid:54)∈ {0, 1}

Consideramos los cuatro casos posibles:
1. Cuando n = 0: izq = mod2 0 = 0 %2 = 0 y der = 0. Por lo tanto

la ecuación vale en este caso.

2. Cuando n = 1: izq = mod2 1 = 1 %2 = 1 y der = 1. Por lo tanto
3. Cuando n > 1: izq = mod2 n = n %2 y der = mod2 (n − 2) =
4. Por útliimo, cuando n < 0: izq = mod2 n =⊥ y der = mod2 (n−

la ecuación vale en este caso también.
(n − 2) %2 = n %2. Vale en este caso también.
2) =⊥. Vale en este caso también, o sea siempre.

3

Por lo tanto, mod2 es solución de la ecuación (ER). ¿Es mod2 la
única solución de esa ecuación? No, por ejemplo la función modRara:

 n %2 si n ≥ 0

−5
7

modRara n =

si n < 0 y n es par
si n < 0 y n es impar

también la satisface.
En realidad modRara plantea la forma más general de las soluciones
de la ecuación (ER), −5 y 7 pueden cambiarse por cualquier par de
valores de Z⊥. Si ambos se cambian por ⊥, se obtiene mod2.

¿Cómo hacemos para señalar "la"solución que nos interesa (en este
caso mod2)? Si sólo escribimos la ecuación, como hemos visto, no al-
canza. Daremos solución este problema incorporando las herramientas
matemáticas adecuadas.
La idea es la siguiente: vamos a inventar un orden parcial entre los
elementos de forma tal que ⊥ sea menor que todos los demás. Y cada
vez que escribamos una ecuación como (ER), diremos que nos interesa
la menor solución posible. Eso excluirá por ejemplo a modRara, ya que
son mayores que mod2, pues se obtienen de mod2 reemplazando ⊥ por
otras cosas.

El sentido del orden es el siguiente. modRara como cualquier otro va-
riante son demasiado informativas dado que contienen información
(el −5, el 7) que no surge de la ecuación (ER). En ese sentido, mod2
es la que menor información contiene ya que no agrega información a
la que hay en la ecuación. El símbolo ⊥, utilizado para representar la
no terminación, representa la ausencia completa de información. Esto
se ajusta a la realidad: un programa que no termina no da ninguna
información, ni siquiera da la información de que no termina.

Preguntas.

1. Considere la siguiente ecuación de tipo (ER)



f n =

1
f (−n)
f (n − 2)
f (−n − 2)
f (n − 1)

si n = 1
si n es par
si n es mútiplo positivo impar de 3
si n es mútiplo negativo impar de 3
caso contrario (c.c.)

¿Qué infomación dá la siguiente ecuación sobre el valor que puede
adoptar f (una función que la satisface) en cada entero? Esto es,
dada una solución sol de la ecuación funcional: ¿para qué valores
n se tiene que sol n está determinado por la ecuación?

Defina si es posibles otras soluciones distintas de la "menor".
2. ¿Si f = F (f ) es una ecuación recursiva del tipo (ER), qué ope-

raciones puede involucrar F ? Dé varios ejemplos de F .

3. Según lo visto hasta el momento, ¿qué puede decir sobre el sig-

nificado de una ecuación de la forma f = F (f )?

2. Órdenes parciales y dominios

Un orden parcial es una relación reflexiva, antisimétrica y tran-
sitiva. Ejemplos: N con ≤, Z con ≤, Q con ≤, R con ≤, P(X) con
⊆ son ejemplos de órdenes parciales (también se dice, de conjuntos
parcialmente ordenados). Cualquier conjunto X con = (la menor
relación reflexiva) es un orden parcial. Se lo llama, el orden discreto.

Gráficamente, Z con ≤:

...
3
2
1

0−1−2−3

4

menor)?

¿Cuál sería la solución que "no inventa información"(o sea la

...
Gráficamente, Z con el orden discreto:

. . . −3 −2 −1 0 1 2 3 . . .

Espacio ordenado de Funciones. Si Y con ≤Y es un orden parcial, el
espacio de funciones de X → Y es un orden parcial con ≤ definido así:

f ≤ g sii ∀x ∈ X. f x ≤Y g x

para f, g ∈ X → Y . Demostrar que ≤ es reflexiva, antisimétrica y
transitiva.
Lifting. Si X es un orden parcial con ≤X, X⊥ (que se define como
X ∪ {⊥}) también es un orden parcial con ≤ definido así:

x ≤ y sii x ≤X y ∨ x =⊥

para x, y ∈ X⊥. Demostrar que ≤ es reflexiva, antisimétrica y transiti-
va.
Si X es el orden discreto, X⊥ se llama llano. Si lifteamos Z con el

orden discreto, obtenemos el siguiente orden llano:

5

3 . . .

. . . −3 −2 −1 0 1

. . .

2
/ . . .

\

|
⊥

Infinito. Si X es un orden parcial con ≤X, X∞ (que se define como
X ∪ {∞}) también es un orden parcial con ≤ definido así:

x ≤ y sii x ≤X y ∨ y = ∞

Demostrar que ≤ es reflexiva, antisimétrica y transitiva.
Supremo. Dado un subconjunto Q ⊆ P donde P con ≤ es un orden
parcial, el supremo de Q (se escribe sup(Q)) es el elemento de P que
satisface:

sup(Q) es cota superior de Q, y
sup(Q) es menor que cualquier otra cota superior de Q.

En símbolos se escribe así:
∀q ∈ Q . q ≤ sup(Q), y
∀p ∈ P . (∀q ∈ Q . q ≤ p) ⇒ sup(Q) ≤ p.

El sup(Q) puede no existir (por ejemplo, en N con ≤, el supremo del
conjunto de todos los números pares no existe). Pero en los casos en
que el supremo existe, es único (demostrar). Cuando existe, decimos
que Q tiene supremo (que puede no estar en Q, está en P ).
Cadenas. En un orden parcial P con ≤, una cadena es una secuencia
infinita p0 ≤ p1 ≤ p2 ≤ . . . ≤ pn ≤ . . . de elementos de P . Si el conjunto
{p0, p1, p2, . . . , pn. . . .} es infinito, se dice que la cadena es interesante.
Si dicho conjunto es finito, se dice que la cadena es no interesante.
Claramente la cadena es no interesante sii a partir de cierto punto la
secuencia no hace más que repetir indefinidamente un elemento.

Obviamente, una cadena no interesante siempre tiene supremo: es el

elemento que se repite indefinidamente.
Ejemplos. En N con ≤, 0 ≤ 2 ≤ 4 ≤ 6 ≤ . . . ≤ 20 ≤ 22 ≤ . . . es una
cadena interesante. No tiene supremo.
En N con ≤, 0 ≤ 2 ≤ 4 ≤ 4 ≤ . . . ≤ 4 ≤ 4 ≤ . . . es una cadena no

interesante. Su supremo es 4.

Un orden discreto sólo tiene cadenas no interesantes. Más aún, las

cadenas son repeticiones indefinidas de un único elemento.
Un orden llano sólo tiene cadenas no interesantes. Hay dos formas
de cadenas: las que consisten de repetir indefinidamente ⊥, y las que
consisten de repetir ⊥ solamente una cantidad finita de veces (0 o más)
y luego repiten otro elemento indefinidamente.

6

Si tomamos N con ≤N el operador relacional usual de los naturales,
y consideramos N∞ con ≤ como se definió más arriba 0 ≤ 2 ≤ 4 ≤
6 ≤ . . . ≤ 20 ≤ 22 ≤ . . . es una cadena interesante con supremo. El
supremo es ∞. Dar un ejemplo de cadena no interesante que tenga
como supremo a ∞.
Si X es finito, P(X) con ⊆ no tiene cadenas interesantes. ¿cuántos
elementos diferentes puede tener una cadena?. Si X es infinito, tiene
cadenas interesantes. Todas ellas tienen supremo. ¿cuál?
Como vimos, N → N⊥ es un orden parcial, donde N⊥ es el orden
llano. La secuencia f0 ≤ f1 ≤ f2 ≤ . . . ≤ fn ≤ . . . es una cadena
interesante, donde fi se define de la siguiente forma

(cid:26) n

⊥

fi n =

si n < i
caso contrario

Esta cadena tiene como supremo a la función identidad.

Predominios. Un predominio es un orden parcial P tal que todas las
cadenas tienen supremo. Como las cadenas no interesantes siempre tie-
nen supremo, puede redefinirse así: “un predominio es un orden parcial
P tal que todas las cadenas interesantes tie