Tema 2: Diseño de algoritmos recursivos

Recursividad

La recursividad y la iteración son los dos mecanismos de los lenguajes para repetir cálculos. Una función es recursiva si se llama a sí misma en su definición.

Tiene la misma potencia expresiva que la iteración: se pueden describir los mismos cómputos.
Da algoritmos más compactos.
Cuesta menos razonar en recursivo que en iterativo, y luego se puede pasar a iterativo sin perder corrección ni eficiencia.

La idea viene de las matemáticas, donde muchas definiciones son recursivas:

n! = \begin{cases} 1 & n = 0 \quad \text{(caso base)} \\ n \cdot (n-1)! & n > 0 \quad \text{(caso general)} \end{cases}

Igual que en una demostración por inducción, al diseñar una función recursiva se puede suponer que el problema ya está resuelto para un tamaño menor.

Iterativo frente a recursivo

Problema: resolver un problema $P$ sobre unos datos $D$ .

Iterativo: resolver $n$ veces un problema más simple $p$ sobre datos $d$ . En el factorial, $p$ es multiplicar dos números, repetido $n$ veces.
Recursivo: resolver $P$ sobre $D$ a partir de $P$ sobre unos datos más pequeños $D'$ . A su vez $D'$ se resuelve con $D''$ , y así se forma una sucesión $D > D' > D'' > \dots > D_t$ que acaba en un caso que se resuelve directamente.

Q ≡ { n ≥ 0 }
Función FACTORIAL (n: entero) retorna (f: entero)
  caso
    n = 0 → 1
    n > 0 → FACTORIAL(n-1) * n
  fcaso
ffunción

La precondición $Q$ caracteriza los estados iniciales para los que el algoritmo funciona.

Para llegar a esto: si se conoce $(n-1)!$ , entonces $n! = (n-1)! \cdot n$ . Las llamadas forman la cadena $(n), (n-1), \dots, (1), (0)$ : una sucesión estrictamente decreciente y finita que termina en el caso base $n = 0$ .

Traza de FACTORIAL(3)

Las llamadas bajan hasta el caso base y los resultados suben combinándose: $n=3 \to n=2 \to n=1 \to n=0$ ; luego $f = 1$ , $f = 1 \cdot 1 = 1$ , $f = 1 \cdot 2 = 2$ , $f = 2 \cdot 3 = 6$ .

Principio de inducción

Es la base teórica que garantiza que el planteamiento recursivo es correcto. Permite demostrar que una propiedad $P$ se cumple para todos los naturales a partir de uno dado, en tres fases: base, recurrencia y conclusión.

Inducción débil (1.ª forma)

Base: $P$ es cierta para un natural $b$ .
Recurrencia (la propiedad es hereditaria):
- Hipótesis: $P$ es cierta para un natural cualquiera $n \ge b$ .
- Tesis: $P$ es cierta para $n + 1$ .
Conclusión: $P$ es cierta para todo natural $\ge b$ .

$10^n - 1$ es divisible por 9 para todo $n \in \mathbb{N}$

Base ( $n = 0$ ): $10^0 - 1 = 0 = 0 \cdot 9$ .
Hipótesis: $10^n - 1 = 9a$ para algún $a \in \mathbb{N}$ , es decir, $10^n = 9a + 1$ .
Tesis: $10^{n+1} - 1 = 10 \cdot 10^n - 1 = 10(9a + 1) - 1 = 90a + 9 = 9(10a + 1)$ , múltiplo de 9.

El truco es escribir el caso $n+1$ en función del caso $n$ para poder usar la hipótesis.

Inducción fuerte (2.ª forma)

Cambia solo la hipótesis: se supone que $P$ es cierta para todos los naturales del intervalo $[b, n]$ , no solo para $n$ .

Todo natural $n \ge 2$ se descompone en producto de primos

Base: 2 es primo ( $2 = 2 \cdot 1$ ).
Hipótesis: la propiedad se cumple para todos los naturales de $[2, n]$ .
Tesis: para $n + 1$ hay dos casos:
- Si es primo, ya está.
- Si no, $n + 1 = a \cdot b$ con $1 < a, b < n + 1$ . Por hipótesis $a$ y $b$ se descomponen en primos, así que $n + 1$ también.

Aquí hace falta la forma fuerte porque $a$ y $b$ no son $n$ , sino números menores cualesquiera.

Inducción noetheriana

Para demostrar propiedades de conjuntos que no son $\mathbb{N}$ : se asocia un natural a cada elemento y se hace inducción sobre ese natural.

Un conjunto de cardinal $n$ tiene $2^n$ partes

Las partes de $U$ son sus subconjuntos: $\mathcal{P}(U) = \{A : A \subseteq U\}$ . Por ejemplo, $\mathcal{P}(\{a, b\}) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}$ .

Inducción sobre el cardinal:

Base: el único conjunto de cardinal 0 es $\varnothing$ , que tiene una parte (él mismo), y $2^0 = 1$ .
Hipótesis: todo conjunto de cardinal $n$ tiene $2^n$ partes.
Tesis: sea $E$ de cardinal $n+1$ , $a \in E$ y $F = E - \{a\}$ , que tiene $n$ elementos. Cada parte de $E$ contiene o no contiene a $a$ :
- Las que no lo contienen son las partes de $F$ : $2^n$ por hipótesis.
- Las que sí lo contienen se obtienen añadiendo $a$ a cada parte de $F$ : otras $2^n$ .
En total, $2^n + 2^n = 2^{n+1}$ .

Con $E = \{a, b, c\}$ : sin $a$ están $\varnothing, \{b\}, \{c\}, \{b, c\}$ , y con $a$ están $\{a\}, \{a, b\}, \{a, c\}, \{a, b, c\}$ .

Conjuntos definidos por recurrencia e inducción estructural

Un conjunto se puede definir:

En extensión: enumerando sus elementos, como $\{1, 3, 5, 7, 9\}$ . Solo si son pocos.
En comprensión: con una propiedad, como $\{x \in \mathbb{N} : 10 \le x < 100 \land \exists y \in \mathbb{N},\ x = 2y\}$ .
Por recurrencia (constructiva):
- Base: los elementos de partida.
- Recurrencia: reglas para crear elementos nuevos a partir de otros ya creados.

Cuando el conjunto está definido por recurrencia se puede razonar directamente sobre esa definición (inducción estructural):

Base: $P$ se cumple para los elementos base.
Hipótesis: los elementos con los que se construye $e$ cumplen $P$ .
Tesis: $e$ cumple $P$ .

Los impares cumplen $X_i = 2i - 1$

Definición recurrente de $X$ : $1 \in X$ , y si $y \in X$ entonces $y + 2 \in X$ .

Base: $X_1 = 1 = 2 \cdot 1 - 1$ .
Hipótesis: $X_i = 2i - 1$ .
Tesis: $X_{i+1} = X_i + 2 = (2i - 1) + 2 = 2(i+1) - 1$ .

Cómo diseñar una función recursiva

Especificar formalmente la función: nombre, dominio y tipo, imagen y tipo, precondición y postcondición.
Elegir el principio de inducción: ver cómo descomponer los datos para obtener la solución a partir de soluciones del mismo problema con datos más pequeños.
Análisis por casos: decidir cuándo el problema es trivial (y qué se devuelve) y cuándo no trivial (y cómo se resuelve).
Escribir el algoritmo en pseudocódigo.
Verificar formalmente que es correcto.

Esquema general

{ Q(x̄) }
función f(x̄: T1) retorna (ȳ: T2)
  caso
    Bt(x̄)  → triv(x̄)
    Bnt(x̄) → c(f(s(x̄)), x̄)
  fcaso
ffunción
{ R(x̄, ȳ) }

$\bar{x}$ e $\bar{y}$ son tuplas de parámetros y resultados.

Elemento	Qué es
$Q$	Precondición: estados válidos para llamar a $f$
$R$	Postcondición: relación entre entrada $\bar{x}$ y resultado $\bar{y}$
$B_t$ , $B_{nt}$	Condiciones de caso trivial y no trivial. Deben excluirse: $B_t(\bar{x}) \land B_{nt}(\bar{x}) \equiv \text{falso}$
$\text{triv} : T_1 \to T_2$	Solución del caso trivial
$s : T_1 \to T_1$	Función sucesor: descompone $\bar{x}$ en el subproblema $\bar{x}' = s(\bar{x})$
$c : T_2 \times T_1 \to T_2$	Función de combinación: junta $\bar{y}' = f(s(\bar{x}))$ con los datos $\bar{x}$

Potencia

Q ≡ { a ≥ 0 ∧ n ≥ 0 }
Funcion POTENCIA (a, n: entero) retorna (p: entero)
  caso
    n = 0 → 1
    n > 0 → POTENCIA(a, n-1) * a
  fcaso
ffunción
R ≡ { p = aⁿ }

Ejercicios propuestos en las diapositivas: número de cifras y suma de cifras de $n$ , Fibonacci, rayuela (de cuántas formas se llega a la casilla $n$ con saltos de 1 o 2), plano (caminos de $(0,0)$ a $(x,y)$ moviéndose solo a la derecha o hacia arriba) y tableros (formas de colocar un tablero $m \times m$ sobre uno $n \times n$ ).

Especificación formal

Se usa la especificación pre/post, basada en lógica de predicados.

Precondición $Q$ : tiene como variables libres los parámetros de entrada y describe en qué estados se puede ejecutar el algoritmo.
Postcondición $R$ : tiene como variables libres la entrada y los resultados, y describe el estado final (la relación entre entrada y salida).

$\{Q\}\ A\ \{R\}$ se lee: si $A$ empieza en un estado que cumple $Q$ , entonces termina, y lo hace en un estado que cumple $R$ .

Cuantificadores

Formato: $(\text{Cuantificador } i)(E(i) : r(i))$ , donde $r(i)$ es el rango y $E(i)$ la expresión.

(\forall i)(A[i] = 3 : 1 \le i \le n) \equiv (A[1] = 3) \land (A[2] = 3) \land \dots \land (A[n] = 3)

(\exists i)(A[i] = 3 : 1 \le i \le n) \equiv (A[1] = 3) \lor (A[2] = 3) \lor \dots \lor (A[n] = 3)

Cuantificador	Ejemplo	Rango vacío
Universal $\forall$	$(\forall i)(A[i] = 3 : 1 \le i \le n)$	cierto
Existencial $\exists$	$(\exists i)(A[i] = 3 : 1 \le i \le n)$	falso
Sumatorio $\Sigma$	$(\Sigma i)(A[i] : 1 \le i \le n)$	$0$
Producto $\Pi$	$(\Pi i)(A[i] : 1 \le i \le n)$	$1$
Máximo $\text{MAX}$	$(\text{MAX } i)(A[i] : 1 \le i \le n)$	—
Mínimo $\text{MIN}$	$(\text{MIN } i)(A[i] : 1 \le i \le n)$	—
Conteo $N$	$(N\, i)(A[i] = 3 : 1 \le i \le n)$	$0$

Rango vacío = elemento neutro

Si ningún $i$ cumple el rango, el resultado es el elemento neutro de la operación: cierto para $\land$ , falso para $\lor$ , $0$ para la suma, $1$ para el producto.

Inmersión

A menudo no se puede diseñar $f$ recursivamente porque no hay forma de descomponer los datos. Por ejemplo, para sumar un vector $A[1..n]$ habría que llamar a la función con un vector "más pequeño", que ya sería de otro tipo.

La solución es definir una función $g$ más general, con más parámetros (o más resultados), que para ciertos valores de esos parámetros calcule lo mismo que $f$ . Es una inmersión de $f$ en $g$ : $g$ es la función inmersora y $f$ la sumergida.

\{Q(\bar{x})\}\ f(\bar{x})\ \{R(\bar{x}, \bar{y})\} \quad\Longrightarrow\quad \{Q'(\bar{x}, \bar{w})\}\ g(\bar{x}, \bar{w})\ \{R'(\bar{x}, \bar{w}, \bar{y})\}

Para obtener $f$ basta con llamar a $g$ con los valores iniciales adecuados de los parámetros nuevos.

Inmersión no final: pasos

Con el ejemplo de la suma, $Q \equiv \{n > 0\}$ y $R \equiv \{e = (\Sigma i)(A[i] : 1 \le i \le n)\}$ :

Obtener $R'$ por sustitución simbólica: cambiar una constante o expresión de $R$ por una variable nueva. Cambiando $n$ por $j$ :

R' \equiv \{e = (\Sigma i)(A[i] : 1 \le i \le j)\}, \qquad R' \land (j = n) \Rightarrow R

Obtener $Q'$ : $Q' \equiv Q \land \text{dominio}(j)$ . Aquí $Q' \equiv \{1 \le j \le n\}$ .
Llamada inicial: el valor de $j$ con el que $g$ calcula lo mismo que $f$ . Aquí $j_{ini} = n$ : $\text{SUMA}(A) = \text{iSUMA}(A, n)$ .
Análisis por casos de la función inmersora.

Para el análisis por casos de iSUMA(A, j): se supone conocida la suma de $A[1..j-1]$ , que es iSUMA(A, j-1), y entonces iSUMA(A, j) = iSUMA(A, j-1) + A[j]. El caso trivial es $j = 1$ , cuya suma es $A[1]$ .

Q' ≡ { 1 ≤ j ≤ n }
Función iSUMA (A[1..n]: vector de enteros, j: entero) retorna (e: entero)
  caso
    j = 1 → A[1]
    j > 1 → iSUMA(A, j-1) + A[j]
  fcaso
ffunción
R' ≡ { e = (Σi)(A[i] : 1 ≤ i ≤ j) }

Llamada inicial: iSUMA(A, n)

Qué constante sustituir

Según qué se sustituya, se recorre el vector de una forma u otra:

Sustitución	Sección	Llamada inicial
$n$ por $j$	$[1..j]$	$j = n$
$1$ por $j$	$[j..n]$	$j = 1$
$1$ por $i$ y $n$ por $j$	$[i..j]$	$i = 1$ , $j = n$

Sustituyendo $1$ por $j$ , la suma queda así: se supone conocida la suma de $A[j+1..n]$ y el caso trivial es $j = n$ .

Q' ≡ { 1 ≤ j ≤ n }
Función iSUMA (A[1..n]: vector de enteros, j: entero) retorna (e: entero)
  caso
    j = n → A[n]
    j < n → iSUMA(A, j+1) + A[j]
  fcaso
ffunción
R' ≡ { e = (Σi)(A[i] : j ≤ i ≤ n) }

Llamada inicial: iSUMA(A, 1)

Rango vacío

Si se permite $n \ge 0$ (vector vacío), el caso trivial pasa a ser la sección vacía, cuya suma es $0$ (el neutro), y el dominio del parámetro nuevo se amplía en uno:

Versión	$Q'$	Caso trivial	Caso no trivial	Llamada inicial
$[1..j]$	$0 \le j \le n$	$j = 0 \to 0$	$j > 0 \to$ `iSUMA(A, j-1) + A[j]`	`iSUMA(A, n)`
$[j..n]$	$1 \le j \le n+1$	$j = n+1 \to 0$	$j < n+1 \to$ `iSUMA(A, j+1) + A[j]`	`iSUMA(A, 1)`

Vector capicúa

$Q \equiv \{n > 0\}$ , $R \equiv \{s = (\forall k)(A[k] = A[n-k+1] : 1 \le k \le n)\}$ .

Sustituyendo $1$ por $i$ y $n$ por $j$ : $Q' \equiv \{1 \le i \le j \le n\}$ , $R' \equiv \{s = (\forall k)(A[k] = A[j-k+i] : i \le k \le j)\}$ .

Función iCAPICUA (A[1..n]: vector de enteros, i, j: entero) retorna (s: booleano)
  caso
    i = j     → VERDADERO
    i = j-1   → (A[i] = A[j])
    i < j-1   → iCAPICUA(A, i+1, j-1) AND (A[i] = A[j])
  fcaso
ffuncion

Llamada inicial: iCAPICUA(A, 1, n). Hacen falta dos casos triviales porque la sección puede quedar con un elemento (longitud impar) o con dos (longitud par).

Con rango vacío ( $n \ge 0$ ), $Q' \equiv \{1 \le i \le j+1 \le n+1\}$ y basta con:

    i > j  → VERDADERO
    i ≤ j  → iCAPICUA(A, i+1, j-1) AND (A[i] = A[j])

Media aritmética

$R \equiv \{e = (\Sigma i)(A[i] : 1 \le i \le n) / n\}$ . Sustituyendo $n$ por $k$ : $Q' \equiv \{1 \le k \le n\}$ y $R' \equiv \{e = (\Sigma i)(A[i] : 1 \le i \le k) / k\}$ .

Si se conoce la media de los $k-1$ primeros, su suma es esa media por $k-1$ :

Función iMEDIA (A[1..n]: vector de reales, k: entero) retorna (e: real)
  caso
    k = 1 → A[1]
    k > 1 → (iMEDIA(A, k-1) * (k-1) + A[k]) / k
  fcaso
ffuncion

Llamada inicial: iMEDIA(A, n).

Matriz simétrica

$R \equiv \{b = (\forall i)((\forall j)(A[i][j] = A[j][i] : 1 \le j \le n) : 1 \le i \le n)\}$ . Sustituyendo $n$ por $k$ se comprueba la submatriz de las filas y columnas $1..k$ , con $Q' \equiv \{1 \le k \le n\}$ .

Si la submatriz $k-1$ es simétrica, solo falta comprobar la nueva "banda" de la fila y columna $k$ :

\text{iSIMETRICA}(A, k) = \text{iSIMETRICA}(A, k-1) \land (A[k][1] = A[1][k]) \land \dots \land (A[k][k-1] = A[k-1][k])

Función iSIMETRICA (A[1..n][1..n]: matriz de enteros; k: entero) retorna (b: booleano)
  si k = 1 entonces retorna VERDADERO
  sino retorna iSIMETRICA(A, k-1) ∧ Banda_Simetrica(A, k)
  fsi
ffunción

{ 2 ≤ k ≤ n }
Función Banda_Simetrica (A[1..n][1..n]: matriz de enteros; k: entero) retorna (b: booleano)
  i = 0
  iguales = VERDADERO
  mientras (i < k-1 ∧ iguales) hacer
    i = i + 1
    si (A[k][i] ≠ A[i][k]) entonces iguales = FALSO fsi
  fmientras
  retorna iguales
ffunción
{ b = (∀i)(A[k][i] = A[i][k] : 1 ≤ i ≤ k-1) }

Llamada inicial: iSIMETRICA(A, n).

Verificación formal

Para garantizar que una función recursiva es correcta hay que demostrar 6 propiedades. Todos los símbolos son los del esquema general.

	Propiedad	Qué garantiza
1	$Q(\bar{x}) \Rightarrow B_t(\bar{x}) \lor B_{nt}(\bar{x})$	Bien definida: en todo estado válido se entra en algún caso
2	$Q(\bar{x}) \land B_{nt}(\bar{x}) \Rightarrow Q(s(\bar{x}))$	Bien definida: la llamada recursiva cumple la precondición
3	$Q(\bar{x}) \land B_t(\bar{x}) \Rightarrow R(\bar{x}, \text{triv}(\bar{x}))$	Base de la inducción: el caso trivial es correcto
4	$Q(\bar{x}) \land B_{nt}(\bar{x}) \land R(s(\bar{x}), \bar{y}') \Rightarrow R(\bar{x}, c(\bar{y}', \bar{x}))$	Paso de inducción: $R(s(\bar{x}), \bar{y}')$ es la hipótesis de inducción
5	Existe $t : D \to \mathbb{Z}$ con $Q(\bar{x}) \Rightarrow t(\bar{x}) \ge 0$	Terminación: la función limitadora está acotada inferiormente
6	$Q(\bar{x}) \land B_{nt}(\bar{x}) \Rightarrow t(s(\bar{x})) < t(\bar{x})$	Terminación: cada llamada hace decrecer $t$

Las 3 y 4 juntas demuestran por inducción que $Q(\bar{x}) \Rightarrow R(\bar{x}, f(\bar{x}))$ para todo $\bar{x}$ . Las 5 y 6 aseguran que las llamadas forman una sucesión estrictamente decreciente y finita, así que la recursión termina.

Ejemplo 1: POTENCIA

$\bar{x} = (a, n)$ , $\bar{y} = p$ , $Q \equiv a \ge 0 \land n \ge 0$ , $R \equiv p = a^n$ , $B_t \equiv n = 0$ , $B_{nt} \equiv n > 0$ , $s(a, n) = (a, n-1)$ , $\text{triv} = 1$ , $c(p', (a, n)) = p' \cdot a$ .

$n \ge 0 \Rightarrow n = 0 \lor n > 0$ ✓
$n \ge 0 \land n > 0 \Rightarrow n - 1 \ge 0$ ✓
$n \ge 0 \land n = 0 \Rightarrow 1 = a^n$ : $a^0 = 1$ ✓
$n > 0 \land p' = a^{n-1} \Rightarrow p' \cdot a = a^n$ : $a^{n-1} \cdot a = a^n$ ✓
$t(a, n) = n$ : $n \ge 0 \Rightarrow n \ge 0$ ✓
$n > 0 \Rightarrow n - 1 < n$ ✓

Ejemplo 2: FACTORIAL

$Q \equiv n \ge 0$ , $R \equiv f = (\Pi i)(i : 1 \le i \le n)$ .

3: con $n = 0$ el rango del producto es vacío, así que vale $1$ , que es lo que devuelve. ✓
4: si $f' = (\Pi i)(i : 1 \le i \le n-1)$ , entonces $f' \cdot n = (\Pi i)(i : 1 \le i \le n)$ . ✓
5 y 6: $t(n) = n$ , igual que en la potencia.

Ejemplo 3: dos llamadas recursivas

{ n ≥ 0 }
Funcion F (n: entero) retorna (p: entero)
  caso
    n = 0 → 1
    n = 1 → 3
    n > 1 → 2 * F(n-1) + 3 * F(n-2)
  fcaso
ffuncion
{ p = 3ⁿ }

Con dos llamadas, las propiedades 2, 4 y 6 se comprueban para cada una, y la 3 para cada caso trivial.

$n \ge 0 \Rightarrow n = 0 \lor n = 1 \lor n > 1$ ✓
$n > 1 \Rightarrow n - 1 \ge 0$ y $n - 2 \ge 0$ ✓
$3^0 = 1$ y $3^1 = 3$ ✓
Con $p'_1 = 3^{n-1}$ y $p'_2 = 3^{n-2}$ : $2 \cdot 3^{n-1} + 3 \cdot 3^{n-2} = 2 \cdot 3^{n-1} + 3^{n-1} = 3 \cdot 3^{n-1} = 3^n$ ✓
$t(n) = n \ge 0$ ✓
$n - 1 < n$ y $n - 2 < n$ ✓

Cómo elegir la función $t$

$t$ mide cuánto queda por hacer: debe ser $\ge 0$ y bajar en cada llamada. Suele ser el tamaño de la sección que falta por procesar.

iSUMA sobre $[1..j]$ (baja con $j - 1$ ): $t(A, j) = j$ .
iSUMA sobre $[j..n]$ (sube con $j + 1$ ): $t(A, j) = n - j + 1$ , el número de elementos de $A[j..n]$ . Con $j = 1$ vale $n$ , y baja en uno en cada llamada.