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:
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$.
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)$.
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"
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;
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").
- 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.
