La recursión es uno de los principios más importantes no sólo de
las matenáticas sino, también, de la informática. Todos los
lenguajes de programación modernos permiten la recursión, y la
usan como una de sus características fundamentales.
La idea de la recusrión es uy sencilla: utilizar, para la solución
de un problema, la solución de una versión más sencilla del
mismo problema, hasta llegar así, reduciendo la dimensión del
problema, a uno tan sencillo que se puede resolver sencillamente.
La manera mejor de entender la recusrión es a través de un
ejemplo. Consideremos un juego muy conocido: el juego de las
torres
de Hanoi. En una table hay tres palos y en uno de ellos hay una
serie de discos de diámetro progresivamente más grande, hasta
formar una especie de pirámide:
El juego consiste en mover la pirámide del palo $1$ al $2$
sin
poner nunca un disco más grande por encima de uno más
pequeño.
Si la torre está formada por $n$ discos, llamaremos el problema
$\mbox{Hanoi}(n)$. Imaginemos ahora que no sabemos como solucionar
$\mbox{Hanoi}(n)$ pero sí sabemos como solucionar el problema más
sencillo con $n-1$ discos: $\mbox{Hanoi}(n-1)$. Con esta solución,
es fácil resolver $\mbox{Hanoi}(n)$. El algoritmo es el siguiente:
- Usa $\mbox{Hanoi}(n-1)$ para mover los $n-1$ discos más
pequeños del palo $1$ al palo $3$.
- Mueve el disco más grande del palo $1$ al palo $2$.
- Usa $\mbox{Hanoi}(n-1)$ para mover los $n-1$ discos más
pequeños del palo $3$ al palo $2$.
El algoritmo se representa esquemáticamente como en Figura 2.
En realidad no hemos resuelto mucho: no sabemos como resolver
$\mbox{Hanoi}(n-1)$. Pero, bueno, si sabemos como resolver
$\mbox{Hanoi}(n-2)$ podemos usar el mismo algoritmo para resolver
$\mbox{Hanoi}(n-1)$. ¿Y cómo resolvemos $\mbox{Hanoi}(n-2)$? Bueno,
si sabemos como resolver $\mbox{Hanoi}(n-3)$...
Seguimos así hasta llegar a $\mbox{Hanoi}(1)$, el problema con
sólo un disco. Y si sólo hay un disco, el problema es sencillo:
movemos el disco desde el palo donde está al palo donde lo queremos
y ya está.
La idea que hemos usado para resolver el problema de las torres de
Hanoi es muy general. En informática es una idea que hace muy
fácil escribir programas, en matemática se relaciona con uno de
los principios más importantes de las matemáticas de los números
enteros, el principio de inducción. Consideremos primero el problema
desde el punto de vista de un programador.
Para los programadores
Las características de los problemas recursivos hace muy fácil
programar soluciones para problemas aparentemente muy complicado como
la torre de Hanoi. En este caso, escribir un programa que nos diga,
paso a paso como mover los discos sería, sin recursión,
extremadamente complicado (los que tienen buenos conocimientos de
programación pueden intentarlo: el programa se puede escribir, pero
es muy complicado de escribir y muy difícil de intender). Por otro
lado, escribir un programa recursivo es muy fácil.
Queremos escribir una función, que llamaremos
hanoi($n$, $a$,
$b$, $c$). La función, como vemos, recibe cuatro
parámetros. El primer parámetro ($n$) es el número de discos que
tenemos que mover, el segundo ($a$) es al palo en que están los
discos, el tercero ($b$) es el palo en que queremos mover los discos,
finalmente, el cuarto ($c$) es el tercer palo, que, si lo necesitamos,
podemos usar como auxilio para mover los discos de $a$ a $b$. La
función, escrita en un \dqt{psudo-código} bastante fácil de
entender
♱ es la siguiente:
hanoi(n, a, b, c)
if n = 1 then
print "mueve un disco de " a " a " b
else
hanoi(n-1, a, c, b)
print "mueve un disco de " a " a " b
hanoi(n-1, c, b, a)
Esto es todo. Si $n=1$, sólo hay que mover un disco, por tanto
imprimimos en pantalla que hay que mover un disco desde el palo fuente
al palo destino. Si no, la función se llama a si misma para mover
$n-1$ discos de la fuente al palo intermedio, mueve al disco más
grande (que ahora ha quedado al descubierto) del palo fuente al palo
destino, y luego vuelve a mover los $n-1$ discos que se había
quitado del medio del palo auxiliario al palo destino. Y el programa funciona. Si ejecutamos la función
hanoi(5, 1, 2, 3) (mueve una torre de cinco discos del palo 1
al palo 2 usando 3 como auxilio), conseguimos la respuesta siguiente:
mueve un disco de 1 a 2
mueve un disco de 1 a 3
mueve un disco de 2 a 3
mueve un disco de 1 a 2
mueve un disco de 3 a 1
mueve un disco de 3 a 2
mueve un disco de 1 a 2
mueve un disco de 1 a 3
mueve un disco de 2 a 3
mueve un disco de 2 a 1
mueve un disco de 3 a 1
mueve un disco de 2 a 3
mueve un disco de 1 a 2
mueve un disco de 1 a 3
mueve un disco de 2 a 3
mueve un disco de 1 a 2
mueve un disco de 3 a 1
mueve un disco de 3 a 2
mueve un disco de 1 a 2
mueve un disco de 3 a 1
mueve un disco de 2 a 3
mueve un disco de 2 a 1
mueve un disco de 3 a 1
mueve un disco de 3 a 2
mueve un disco de 1 a 2
mueve un disco de 1 a 3
mueve un disco de 2 a 3
mueve un disco de 1 a 2
mueve un disco de 3 a 1
mueve un disco de 3 a 2
mueve un disco de 1 a 2
Si alguien tiene la paciencia de probarlo, verá que, efectivamente,
las instrucciones son correctas.
Para los matemáticos
Una cosa puede haber llamado la atención en el ejemplo precedente:
hay muchos movimientos. Incluso para mover una torre de sólo cinco
discos, son necesarios muchos movimientos. Es natural (para un
matemático, por lo menos) preguntarse: Cuántos movimientos
necesito para mover una torre de $n$ discos, donde $n$ puede ser
cualquiera?
Para descubrirlo, llamemos $H(n)$ el número de movimientos
necesarios para mover una torre de $n$ discos. Si sólo tenemos un
disco, la cosa es fácil: simplemente movemos el disco de un palo al
otro. Por tanto:
\begin{equation}
H(1) = 1
\end{equation}
Para cualquier $n$ construimos una ecuación recursiva. Para mover
una torre de $n$ discos del palo $1$ al palo $2$, tenemos que hacer
tres operaciones:
- mover una torre de $n-1$ discos de $1$ a $3$; el número de
movimientos necesarios es $H(n-1)$;
- mover el disco que queda de $1$ a $2$: un movimiento;
- mover una torre de $n-1$ discos de $3$ a $2$; el número de
movimientos necesarios es $H(n-1)$.
Sumando todos los movimientos, esto nos da la ecuación recursiva
\begin{equation}
H(n) = 2\cdot H(n-1) + 1
\end{equation}
Con estas dos ecuaciones, podemos calcular el número de movimientos
necesario por cualquier $n$:
\begin{equation}
\begin{aligned}
H(1) &= 1~~~\mbox{esto ya lo sabíamos} \\
H(2) &= 2H(1) + 1 = 2 + 1 = 3 \\
H(3) &= 2H(2) + 1 = 2\cdots 3 + 1 = 7 \\
H(4) &= 2H(3) + 1 = 2\cdots 7 + 1 = 15 \\
H(5) &= 2H(4) + 1 = 2\cdots 15 + 1 = 31
\vdots
\end{aligned}
\end{equation}
Con este método podemos calcular el número de movimientos
necesarios para cualquier número de discos. Es fácil continuar y
darse cuenta, por ejemplo, que para mover una torre de $10$ discos son
necesarios nada menos que $1023$ movimiento y para una torre de 20
discos un imposible $1.048.575$ movimientos.
Esto nos puede satisfafer, pero seguramente no satisface a un
matemático. Lo que un matemático busca es una fórmula directa,
algo no recursivo, algo que, por cada número $n$, nos dice,
directamente y sin tantos rodeos, cuantos movimientos necesitamos. (No
siempre los matemáticos lo consiguen, pero en este caso veremos que
sí, que se puede conseguir).
Empecemos notando que los números que hemos conseguido tienen una
particularidad: si los aumentamos de una unidad, conseguimos siempre
potencias de $2$: $1+1=2=2^1$, $3+1=4=2^2$, y siguiendo
$31+1=32=2^5$. Lo mismo vale para los otros valores que hemos
mencionado: $1.023+1=1.024=2^{10}$ y
$1.048.575+1=1.048.576=2^{20}$. No sólo: notamos que el exponente de
$2$ siempre es igual al argumento de la función $H$. Así, por ejemplo
\begin{equation}
\begin{aligned}
H(3) + 1 &= 7 + 1 = 8 = 2^3 \\
H(5) + 1 &= 31 + 1 = 32 = 2^5 \\
H(10) + 1 &= 1.023 + 1 = 1.024 = 2^{10}
\end{aligned}
\end{equation}
Esto nos da una idea: es posible que hayamos encontrado la regla
general, y que podamos escribir, por cada número $n$
\begin{equation}
H(n) = 2^n - 1
\end{equation}
Es posible (y, de hecho, es así). Pero un buen matemático no se
conforma con ser posible: un buen matemático necesita
demostrarlo. Para hacer esto, dejamos de un lado por el momento
nuestra ecuación y nos ocupamos de un método de demostración muy
útil, muy relacionado con la recursión, y que nos permitirá
demostrar nuestra hipótesis: el
método de inducción.
El método de inducción
El método de inducción es un instrumento potente y en aparencia
sencillo, pero la lógica que está detrás de su aplicación es
sorprendentemente sutil. Empecemos con su definición. Consideremos
una propiedad $P$ que los números enteros pueden o no tener, y
escribamos $P(n)$ para indicar que el número $n$ tiene la
propiedad. $P$ puede representar muchas propiedades. Por ejemplo:
- $P(n)$ quiere decir "$n$ es un número primo"♯;
- $P(n)$ quiere decir "$n$ es impar";
- $P(n)$ quiere decir $n>0$;
- $P(n)$ quiere decir "$2n$ es par;"
- $P(n)$ quiere decir "una torre de Hanoi con $n$ discos se puede mover en $2^n-1$ movimientos"
Algunas de estas propiedades son ciertas por todos números (todos
números enteros son mayores de cero, y su doble es par), otras no
(no todos los números son primos, ni todos son impares).
Propiedades como $P$ también tienen propiedades. En particular,
llamaremos una propiedad
hereditaria si lo siguiente es
ciertos:
por cada número $n$, si $n$ tiene la propiedad, entonces
$n+1$ también la tiene. En lógica esto se escribe:
\begin{equation}
\forall n. P(n) \Rightarrow P(n+1)
\end{equation}
(el símbolo $\forall$ singifica "para todos": con esto afirmamos que
lo que sigue es cierto por todo $n$, el símbolo $\Rightarrow$ quiere
decir "implica": afirma que si el predicado que precede el símbolo
es cierto, el predicado que lo sigue también lo es).
Es fácil ver, por ejemplo, que la propiedad 3 es hereditaria: si un
número $n$ es mayor de cero y consideramos el número $n+1$
obtenido añadiendo una unidad a $n$, ese número también será
mayor de cero. Por otro lado, la propiedad 2 no lo es: si $n$ es impar
(por ejemplo, si $n=3$) entonces $n+1$ ($4$, en este caso) es par.
El principio de inducción nos dice lo siguiente:
Dada una propiedad $P$, si $P$ es válida en el caso de $n=1$, y $P$
es hereditaria, entonces $P$ es válida para todo número entero.
La intuición confirma el principio. Digamos, por ejemplo, que
queremos demostrar que la propiedad es válida en el caso
$n=5$. Procedemos así:
- $P$ es cierto en el caso de $n=1$, es decir, $P(1)$;
- Si $P(1)$ es cierto, entonces $P(2)$ es cierto;
- Si $P(2)$ es cierto, entonces $P(3)$ es cierto;
- Si $P(3)$ es cierto, entonces $P(4)$ es cierto;
- Si $P(4)$ es cierto, entonces $P(5)$ es cierto;
Por tanto, si $P$ respeta los requisitos del principio de inducción,
$P(5)$ es cierto. De la misma manera podemos (idealmente) aplicar el
principio para demostrar que $P(n)$ es cierto sea cual sea $n$
*.
Este principio nos proporciona una manera muy útil para demostrar
teoremas. Tenemos una propiedad $P$ que queremos demostrar (por
ejemplo, quereoms demostrar que el doble de cada número $n$ es
par). Para demostrarla tenemos que demostrar que cumple las
hipótesis del principio de inducción, es decir, tenemos que
demostrar que:
- La propiedad es cierta en el caso $n=1$ (esto se llama el "caso base")
- Si asumimos que la propiedad es cierta en el caso $n$ (es decir:
asumimos por hipótesis que $P(n)$ es cierto), entonces la propiedad
es cierta en el caso $n+1$ (es decir: si $P(n)$ s cierto, entonces
$P(n+1)$ también es cierto, esto es el "caso de inducción").
Si conseguimos demostrar estas dos cosas, entonces hemos demostrado
que la propiedad $P$ es cierta por cada número. Considereos un
ejemplo: queremos demostrar que, por cada $n$, $2n+1$ es
impar. Tenemos los dos casos:
- Caso base: $n=1$. En este caso $2n+1=3$, y sabemos que $3$ es
impar.
- Inducción: suponemos que la propuedad es cierta para $n$, es
decir, supongamos que $2n+1$ es impar. Tenemos que demostrar que
$2(n+1)+1$ es impar. Procedemos como sigue:
\begin{equation}
2(n+1)+1 = 2n + 2 + 1 = 2n+1 + 2
\end{equation}
Ahora, sabemos que $2n+1$ es impar, por tanto en esa ecuación
tenemos un número impar (lo llamamos $m$) a que le añadimos
$2$. Dado que $m$ es impar, su succesor, $m+1$ es par y por tanto
su succesor $m+1+1=m+2$ es impar.
De vuelta a Hanoi
Tenemos ahora los instrumentos para demostrar que nuestra solución
del número de movimientos necesarios para mover una torre es
correcta. Sólo tenemos que reformular nuestro descubrimiento como
una propiedad de los números enteros. La propiedad es la siguiente:
El número $n$ tiene la propiedad de Hanoi ($H(n)$) si es posible
mover una torre de Hanoi de $n$ discos usando $H(n)=2^n-1$
movimientos.
Recordamos que $H(n)$ es el resultado de la ecuación recursiva
\begin{equation}
H(n) = 2\cdot H(n-1) + 1
\end{equation}
que asumimos válida. Empecemos la demostración con los dos pasos
- Paso base $n=1$. Sabemos que podemos mover una torre de un solo
disco con un solo movimientos. Dado que $H(1)=2^1-1=1$, la propiedad
se cumple en el caso de $n=1$.
- Paso de inducción. Supongamos ahora que la propiedad sea
cierta para $n$, es decir, que $H(n)=2^n-1$. Queremos demostrar
que $H(n+1)=2^{n+1}-1$. Para esto, aplicamos la recursión:
\begin{equation}
\begin{array}{rcll}
H(n+1) & = & 2H(n) + 1 & \mbox{ecuación recursiva} \\
& = & 2(2^n-1) + 1 & \mbox{hypótesis inductiva} \\
& = & 2\cdots2^n - 2 + 1 & \\
& = & 2^{n+1} - 1
\end{array}
\end{equation}
La igualdad crucial es la segunda: podemos remplazar $H(n)$ con
$2^n-1$ porque el método de inducción nos permite asumir que
la propiedad es cierta para $n$, es decir, asumimos ya como
demostrado que $H(n)=2^n-1$ y usamos este hecho para demostrar que
$H(n+1)=2^{n+1}-1$. El resto es álgebra.
♱ El pseudo código es un instrumento que los programadores usan a
menudo para describir un problema. Se trata de una notación
simplificada que evita todos los detalles necesarios para que un
programa efectivamente funcione y que pone el foco en sus aspectos
esenciales.
♯ Recordamos aquí que un número es
primo si sólo se puede
dividir por el número mismo y por $1$. Los números $2$, $3$, $5$,
$7$, $11$, etc. son primos (por convención, el número $1$ no se
considera primo), mientras, por ejemplo, $6$ y $9$ no lo son (el
primero se puede dividir por $2$ y $3$, el segundo por $3$). Uno de
los descubrimientos más sorprendente de los matemáticos griegos es
que existe una infinidad de números primos: dado un número
cualquiera, existe un número primo más grande que este número.
*
Para los más lógicos: cuando he dicho que es obvio que la
propiedad de inducción garantiza que $P$ es cierto para todos los
números enteros, en realidad he engañado. Hay muchas sutilezas
lógicas detrás del principio de inducción en que en ese momento
no voy a entrar.
Esencialmente, lo que he demostrado con mi argumento intuitivo es que,
dado cualquier número finito $n$, puedo demostrar que $P(n)$ es
cierto. Pero esto es muy distinto que afirmar que $P$ es cierto en el
caso de la infinidad de números enteros.
Una solución a este problema lógico es la de los
llamados
axiomas de Peano, que describen propiedades tan
básicas de los números enteros que se asumen sin demostrar
(propiedades como "cero es un número"). Uno de los axiomas de Peano
es precisamente el principio de inducción. En este caso, los
problemas lógicos desvanecen: simplemente definimos los números
enteros como esos números para que vale el principio de inducción.
