Fundamentos

Funciones recursivas

Fundamentos Nivel medio

Seguimos ampliando el tema de las funciones para hablar, en esta ocasión, de las funciones recursivas. La recursión es un concepto que suele atragantarse cuando se está aprendiendo a programar, pero puede ser una herramienta muy potente, aunque también peligrosa si no la controlamos correctamente.

Si recordamos, en el artículo de utilidades para validar formularios utilizábamos una función recursiva a la que llamamos isEmpty. Es hora, pues, de ver cómo funcionaba.

¿Qué son las funciones recursivas?

Planteemos la siguiente situación. Creamos una función que llamaremos A que haga unas ciertas tareas y, para ello, llama a otra función, que llamaremos B, como ya vimos que se podía hacer. A continuación, en el código de esa función B llamamos también a la función A. ¿Es posible? Sí, estamos haciendo una recursión.

Pese al ejemplo, lo más común en la recursividad es una función que, atención, se llama a sí misma (recursión directa, pues el ejemplo del párrafo anterior es una recursión indirecta). Es el propio concepto de recursión, es decir, el hecho de que esa función que realiza unas ciertas tareas a partir de unos datos iniciales, se llame a sí misma, obviamente con otros datos iniciales. ¿Y cuándo acabaría la función si continuamente se está llamando a sí misma? Ahí es donde, como programadores, debemos diseñar bien las funciones recursivas para que no entremos en bucles infinitos como vimos que nos podía pasar con las estructuras de control.

Toda función recursiva tiene una versión iterativa

Esta afirmación es cierta, pues siempre vamos a encontrar un algoritmo que utilice métodos iterativos (como los bucles WHILE o los bucles FOR) para obtener la misma solución. Sin embargo, a veces es una solución bastante difícil de encontrar o muy compleja de seguir, por lo que con una función recursiva podemos tener cierta elegancia.

Para ver cómo estructurar funciones recursivas, vamos a realizar cuatro ejemplos en donde podremos ver cómo actúan este tipo de funciones. En estos ejemplos calcularemos el factorial de un número, veremos los números de Fibonacci, utilizaremos el algoritmo de Euclides y acabaremos con las torres de Hanoi.

Obtener el factorial recursivamente

Recordemos lo que es el factorial de un número. Es aquel que surge de la multiplicación de todos los números enteros positivos desde 1 hasta el número proporcionado. Es decir, que para calcular el factorial de 5 tendríamos la multiplicación 5 * 4 * 3 * 2 * 1 y el factorial sería 120.

Expresar el problema de forma recursiva

¿Podríamos expresar el problema del factorial de una forma recursiva? Es evidente que de forma iterativa es muy fácil, pues en este caso nos basta con recorrer los números desde el proporcionado, el 5, hasta el 1, restando de uno en uno en cada ocasión. Pero ésta sería la forma iterativa y, nosotros, ahora mismo estamos buscando la forma recursiva.

Pensemos un momento. Si tengo el 5, el siguiente número será él mismo menos la unidad. Y el siguiente número volverá a ser el nuevo número (4 en este caso) menos la unidad, desde el cual sacaremos el factorial. Llegaríamos así hasta llegar al número 1, que es el último y donde acabaríamos. Podemos, entonces, pensar que el factorial de 5 es realmente el factorial de 4 multiplicado por 5. Y llegamos también a la conclusión de que el factorial de 4 es realmente el factorial de 3 multiplicado por 4. Para después pensar que el factorial de 3 será el factorial de 2 multiplicado por 1. Y, al final, el factorial de 1 es él mismo, así que terminamos. ¡Estamos “trozeando” el problema pero siempre calculando nuevos factoriales!

Por tanto, ahí es donde hemos conseguido obtener nuestra función recursiva, que vamos a implementar en pseudocódigo a continuación.

FUNCION factorial(n) {
  IF (n == 0 OR n == 1) {
    resultado = 1
  } ELSE IF (n > 1) {
    resultado = n * factorial(n-1)
  }
  DEVOLVER resultado
}

La importancia de la condición de parada

Es especialmente importante en una función recursiva el llegar a un punto donde, de por sí, ya le estamos dando el resultado final. En este caso ese punto es cuando el valor de n es igual a 0 o a 1. Si no colocamos esa condición de parada, ese resultado ya conocido, la función recursiva no acabaría nunca o llegaría a un caso donde no sabe cómo responder y moriría dando un error o entrando en un bucle infinito. Veamos una traza para ver qué hacen realmente las instrucciones que hemos colocado.

Una traza de la solución

Mediante un listado vamos a ver qué está ocurriendo en cada paso:

  1. Queremos obtener el valor del factorial de 5, así que utilizamos la función definida y preguntamos por factorial(5)
  2. En la función llegamos a que 5 es mayor que 1, por tanto el resultado es el propio 5 multiplicado por…, por el factorial de 4, es decir, por factorial(4)
  3. En fin, vayamos pues a calcular factorial(4) dejando en “pausa” el factorial de 5 en el punto donde se debe calcular el de 4. Entramos de nuevo en la función, volvemos a ver que 4 es mayor que 1 y tenemos que el factorial de 4 equivale a 4 multiplicado por…, por el factorial de 3
  4. Tendremos que seguir, así que vayamos a calcular factorial(3) para ver si nos saca de dudas. El 3 es mayor que 1, así que el resultado es 3 multiplicado por…, por el factorial de 2
  5. Tocará saber factorial(2) para obtener la solución. Sí, el 2 también parece que es mayor que 1, por tanto el resultado del factorial de 2 es el propio 2 multiplicado por…, por el factorial de 1
  6. No queda otra que calcular factorial(1) si queremos llegar a un resultado. En este caso, ¡anda!, tenemos un resultado definitivo. Y es que el factorial de 1 lo sabemos y el resultado es 1
  7. Vamos a decírselo a factorial(2), el cual estaba esperando el resultado de factorial(1). Ahora que ya lo tenemos, puede calcular que su factorial es 2 multiplicado por 1, con lo que concluye que su resultado es 2 y corre a decírselo a factorial(3)
  8. Teníamos esperando también a factorial(3) al que ahora le decimos que factorial(2) es 2, así que utiliza este número, lo multiplica por 3 y su resultado es que el factorial de 3 es 6
  9. Con este resultado, puede avisar a factorial(4) que, ahora sí, ya puede saber que el factorial de 4 se consigue multiplicado 4 por 6, que es el resultado que le ha dado factorial(3). Así, ya sabe que es 24
  10. Finalmente, éste le dice a factorial(5) su resultado, y por fin podemos conocer el factorial de 5, que será 5 multiplicado por 24, es decir, 120. ¡Ya hemos conseguido llegar al resultado definitivo!

Como veis, queda claro cómo actúa una función recursiva. En su interior llegará un momento donde puede “reducir” su problema a otro menor pero de las mismas características, con lo que se llama a sí misma para obtener el resultado. Por ello, siempre debe haber un resultado conocido y básico desde el que ir tirando de la cuerda. Vamos a seguir viendo funciones recursivas para verlo mejor.

Los números de Fibonacci

La sucesión de Fibonacci es bien conocida en matemáticas y representa una serie de números que, a raíz de una situación inicial en la que los dos primeros números tienen valor 1, los siguientes números se construyen sumando los dos últimos números. Así, el principio de la serie de Fibonacci es:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, …

O sea, que el tercer número es la suma de los dos anteriores, 1+1. El cuarto número será la suma de 1+2, el quinto será la suma de 2+3, el sexto de 3+5 y así hasta el infinito. La sucesión de Fibonacci es muy conocida en el mundo de la naturaleza, pues muchas formas de las plantas, espirales de la concha de un caracol e incluso árboles genealógicos de las abejas responden a esta sucesión de números.

Expresión recursiva de la sucesión de Fibonacci

¿Podemos expresar este problema con funciones recursivas con algún resultado conocido? Sí, de manera muy sencilla. Los resultados conocidos ya los tenemos, y es que por definición hemos dicho que los dos primeros números serán un 1. Y la recursión vendrá en que, cuando la posición de nuestro número sea mayor a 2, el valor que reside en esa posición será la suma de los dos anteriores. Veamos el algoritmo.

FUNCION fibonacci(n) {
  IF (n == 1 OR n == 2) {
    resultado = 1
  } ELSE IF (n > 2) {
    resultado = fibonacci(n-1) + fibonacci(n-2)
  }
  return resultado
}

Por ejemplo, vayamos ahora a conocer qué número ocupa la sexta posición de la sucesión de Fibonacci.

  1. Queremos conocer fibonacci(6) pero nos dice que, al ser 6 mayor que 2 debemos saber fibonacci(5) y fibonacci(4)
  2. Calculemos pues fibonacci(5) que nos dice que debemos saber fibonacci(4) y fibonacci(3)
  3. Pasemos a calcular fibonacci(4) que querrá saber fibonacci(3) y fibonacci(2)
  4. Pero para saber fibonacci(3) nos pide obtener fibonacci(2) y fibonacci(1)
  5. Vaya, ésta es fácil, pues fibonacci(2) devolverá un 1 y, después, fibonacci(1) devolverá otro 1, con lo que el resultado de fibonacci(3) será un 2
  6. Volvemos adonde fibonacci(4) y nos faltaba por calcular fibonacci(2), el cual devolverá otro 1 y tendremos un resultado de 3 en la cuarta posición
  7. Al seguir hacia atrás, fibonacci(5) esperaba este resultado, así que ahora pasa a calcular de nuevo fibonacci(3) que volverá a consultar a fibonacci(2) y fibonacci(1)
  8. Una vez hechas las nuevas consultas y obtenido el resultado para fibonacci(5), entonces volveremos a fibonacci(6), pero le queda pendiente saber cuánto vale fibonacci(4), así que lo calcula
  9. Éste le volverá a preguntar a fibonacci(3), el cual vuelve a calcular fibonnaci(2) y fibonacci(1) para obtener un valor, y preguntará otra vez a fibonacci(1) para obtener el otro valor
  10. Así, al final fibonacci(6) recibe por fin los dos valores y concluye que 5 más 3 es igual a 8

Parece lioso, de hecho lo es, pero siguiendo del hilo de las llamadas y dejando a las otras “en espera” se puede ver qué va haciendo en cada momento. Con este algoritmo hemos visto un ejemplo de que quizá en este caso es mejor buscar un algoritmo iterativo (de hecho, es mucho mejor en este caso), porque os habréis fijado de que ha llamado varias veces a funciones para conocer valores que ya había calculado antes. Y si el número que pedimos es mucho mayor, aún sería peor. Pero nos sirve para seguir conociendo cosas de las funciones recursivas.

Algoritmo de Euclides

Sigamos con los ejemplos de funciones recursivas para ir asentando, poco a poco, el concepto y ver qué potencial puede llegar a tener. Vamos a utilizar el algoritmo de Euclides, el cual sirve para calcular el máximo común divisor de dos números.

Para resolver el problema y teniendo dos números x e y, este algoritmo se sigue de la siguiente forma: primero calculamos el resto de la división del número mayor entre el menor. Si el resto fuera cero, entonces el máximo común divisor es el menor de ambos números y acabaría el problema (condición de parada). Pero si el resto fuera distinto de cero, entonces llegaremos a la solución calculando el máximo común divisor de otros dos números diferentes, que son el menor de entre x e y y el propio resto que hemos obtenido de la división. Puede que leído sea más complejo que si vemos el programa y lo seguimos. Vamos allá:

FUNCION maximo(a, b) {
  IF (a > b) {
    DEVOLVER a
  }
  DEVOLVER b
}

FUNCION minimo(a, b) {
  IF (a < b) {
    DEVOLVER a
  }
  DEVOLVER b
}

FUNCION maximoComunDivisor(x, y) {
  menor = minimo(x, y)
  mayor = maximo(x, y)
  resto = mayor % menor
  IF (resto == 0) {
    DEVOLVER menor
  }
  DEVOLVER maximoComunDivisor(menor, resto)
}

En esta ocasión, hemos utilizado tres funciones. Una para calcular el máximo, otra para calcular el mínimo y la última es la función recursiva que calculará el máximo común divisor. Vamos a hacer una traza sencilla y veremos qué ocurre. Supongamos que queremos calcular el máximo común divisor de 256 y 114 llamando a maximoComunDivisor(256, 114).

  1. En primer lugar obtenemos el valor más bajo utilizando la función minimo y, posteriormente, obtenemos el más alto con la función maximo. Tenemos, por tanto, el 114 como mínimo y el 256 como máximo
  2. Ahora calculamos el resto con el operador módulo, el cual nos daba el valor del resto de una división. Teniendo el mayor y el menor, realizamos el módulo del 256 sobre el 114 para obtener un resto igual a 28
  3. Como el resto no es igual a 0, volvemos a llamar a maximoComunDivisor, esta vez con los valores 114 (por ser el menor de los dos iniciales) y 28, por ser el resto
  4. Hacemos todos los pasos de obtener el máximo y el mínimo al igual que antes y ahora 114 % 28 nos da como resultado un resto igual a 2
  5. Seguimos adelante, pues el resto sigue sin ser igual a 2, por lo que volvemos a llamar a la función con los valores 28 y 2
  6. Ahora, después de saber cuál es el máximo y el mínimo, el resto nos da como valor un 0. ¡Llegamos al final! Como hemos encontrado un resto 0, es decir, una división exacta, podemos concluir que el mínimo común divisor de 256 y 114 es 2

Como hemos podido ver, hemos utilizado varias veces las funciones minimo y maximo dentro de la propia función recursiva maximoComunDivisor sin ningún problema.

Las torres de Hanoi

Seguro que todos, o casi todos, habéis oído hablar de las torres de Hanoi. Puede que incluso las hayáis tenido o, alguna vez, hayáis intentado resolverlas. El ejemplo básico es el tener cuatro discos (o más), cada uno de un tamaño menor a otro, y obligatoriamente un total de tres torres. Inicialmente tenemos los cuatro discos en una misma torre, pero con la norma de que un disco más pequeño nunca tendrá encima de él a un disco mayor.

El juego consiste en pasar, de uno en uno, todos los discos desde la primera torre hasta la tercera torre. Para ello, por ejemplo comenzamos cogiendo el disco pequeño y lo situamos en una de las libres, luego el siguiente lo situamos en la otra (porque no puede estar encima del pequeño), el siguiente, como es más grande, no lo podremos mover, pero sí podemos colocar el pequeño de nuevo encima del segundo disco y dejar una torre libre… En fin, que es más fácil viéndolo que leyéndolo y estamos seguros de que este juego lo habéis visto muchas veces.

Definición recursiva

Puede costar entender este problema de forma recursiva. De hecho, lo primero que se nos viene a la cabeza nunca es recursivo, ni en este ni en ninguno de los otros casos. “No estamos hechos para pensar recursivamente”, pues nos es un concepto extraño. Así que, pensemos, si tenemos en este ejemplo cuatro discos, podemos reducirlo y pensar en que, primero, deberemos conseguir pasar tres discos. Y ése problema lo podemos reducir a pasar dos discos. Finalmente, el caso base, la condición de parada, sería el caso de un solo disco. Sí, parece que podemos atacar el problema recursivamente. Veamos la función con la solución y luego la seguimos:

FUNCION resolverHanoi(discos, inicial, final, libre) {
  IF (discos == 1) {
    IMPRIMIR 'Mover disco desde ' . inicial . ' hasta ' . final
  }
  ELSE {
    // Primero moveremos discos-1 desde inicial hasta libre
    resolverHanoi(discos-1, inicial, libre, final)
    // A continuación movemos el disco grande en cada momento a su posición final
    IMPRIMIR 'Mover disco desde ' . inicial . ' hasta ' . final
    // Por último moveremos discos-1 desde libre hasta final
    resolverHanoi(discos-1, libre, final, inicial)
  }
}

Ciertamente, parece complejo. Lo veremos mejor con una traza que si tratamos de describirlo con palabras.

Una traza de las torres de Hanoi

Vamos a llamar a resolverHanoi(4, 1, 3, 2), es decir, con cuatro discos, con la posición inicial 1, la posición final 3 y la torre que está libre actualmente siendo la 2. Empecemos la traza:

  1. Al principio vemos que discos no es igual a 1, así que entramos por el ELSE y llamamos a resolverHanoi(3, 1, 2, 3). O sea, hemos reducido un disco, ahora hay 3, la posición inicial sigue siendo 1, la final ahora es 2 (porque queremos que el disco más grande de todos vaya directamente a la posición 3) y la que está libre es la 3
  2. Pasemos, pues a resolver esa nueva llamada (pensad que, lo que viene después que es imprimir no se ejecuta hasta que acaban las llamadas a las funciones previas). Los discos siguen siendo mayores que 1, así que ahora deberíamos llamar a resolverHanoi(2, 1, 3, 2)
  3. Volvemos a ver que los discos aún son mayores que 1, así que llamamos a resolverHanoi(1, 1, 2, 3)
  4. Atención, en este caso ya tenemos sólo un disco. Por tanto, imprimimos Mover disco desde 1 hasta 2
  5. Volvemos al paso anterior, que era cuando teníamos el problema con dos discos. Como ya tenemos el primer resultado mientras íbamos por el ELSE, ahora seguimos y nos encontramos con que debemos imprimir Mover disco desde 1 hasta 3
  6. Llegamos al final de esta función en el que se nos dice que llamemos a resolverHanoi(1, 2, 3, 1), que imprimirá Mover disco desde 2 hasta 3
  7. Al acabar esta función, volveremos algún paso atrás (desde cuando había tres discos) y llegaríamos a que nos imprime, ahora mismo, Mover disco desde 1 hasta 2
  8. Después continuaríamos la ejecución en esa función de llamada a los tres discos y nos diría que resolvamos resolverHanoi(2, 3, 2, 1)
  9. Esta nueva llamada no podría acabar y tendría que llamar a resolverHanoi(1, 3, 1, 2) que imprimirá Mover disco desde 3 hasta 1
  10. Al volver atrás, llegaremos a otra impresión, esta vez Mover disco desde 3 hasta 2
  11. Y luego tendríamos que llamar a resolverHanoi(1, 1, 2, 3)

Hacer trazas de funciones recursivas se puede convertir en un pequeño rompecabezas, pero nos ha servido para ver qué sucedía.

Resultado

Vamos a ver el resultado (líneas en negrita) de haber llegado hasta el final:

  • resolverHanoi(4, 1, 3, 2)
  • resolverHanoi(3, 1, 2, 3)
  • resolverHanoi(2, 1, 3, 2)
  • resolverHanoi(1, 1, 2, 3)
  • Mover disco desde 1 hasta 2
  • Mover disco desde 1 hasta 3
  • resolverHanoi(1, 2, 3, 1)
  • Mover disco desde 2 hasta 3
  • Mover disco desde 1 hasta 2
  • resolverHanoi(2, 3, 2, 1)
  • resolverHanoi(1, 3, 1, 2)
  • Mover disco desde 3 hasta 1
  • Mover disco desde 3 hasta 2
  • resolverHanoi(1, 1, 2, 3)
  • Mover disco desde 1 hasta 2
  • Mover disco desde 1 hasta 3
  • resolverHanoi(3, 2, 3, 1)
  • resolverHanoi(2, 2, 1, 3)
  • resolverHanoi(1, 2, 3, 1)
  • Mover disco desde 2 hasta 3
  • Mover disco desde 2 hasta 1
  • resolverHanoi(1, 3, 1, 2)
  • Mover disco desde 3 hasta 1
  • Mover disco desde 2 hasta 3
  • resolverHanoi(2, 1, 3, 2)
  • resolverHanoi(1, 1, 2, 3)
  • Mover disco desde 1 hasta 2
  • Mover disco desde 1 hasta 3
  • resolverHanoi(1, 2, 3, 1)
  • Mover disco desde 2 hasta 3

Si os fijáis, hasta que no llega al momento en donde sólo hay un disco, no imprime nada por pantalla. Es debido a que no sabe resolver realmente para más de un disco y por eso debe reducir el problema. Es una característica común de las funciones recursivas. Podéis probar esta secuencia de movimientos y veréis que no falla, se han movido los discos de la primera torre a la tercera sin estar nunca uno más grande encima de otro más pequeño.

Si lo implementáis, podéis pedirle, por ejemplo, que resuelva uno de 5, 6, 10, 20 discos. Siempre acertará.

Que la recursividad sea tu aliada

Podríamos seguir y seguir viendo funciones recursivas, pero creo que han sido suficientes ejemplos como para ver qué son y lo que nos pueden aportar las funciones recursivas. Ahora ya depende de tu habilidad como programador el poder introducirlas, o no, pues recuerda que, a veces, una función iterativo será más rápida.

Practicaremos un poco en el próximo reto de A practicar…, pero antes debemos ver un artículo en torno a la ordenación de elementos. Concretamente, un problema referente a la ordenación.

Deja una respuesta