El post de hoy surge de una pregunta que yo mismo me he hecho en alguna ocasión y que, si eres programador como nosotros, te asaltará o te habrá asaltado alguna vez: ¿cuándo utilizo una solución recursiva y cuándo una solución iterativa?. En esta entrada del blog trataremos de dar respuesta a esta cuestión, aunque como sabréis no existe una norma universal acerca de cómo programar.

Antes que nada, me gustaría dar unas nociones básicas para que los lectores con menos experiencia programando entiendan las diferencias entre un algoritmo iterativo y un algoritmo recursivo, apuntando ligeramente sus características para que se entienda el porqué de esta pregunta.

Iterativo vs Recursivo

Por definición, la recursión es una forma de especificar un proceso basándonos en su propia definición. Para que puedas entenderlo mejor, si tenemos un problema de tamaño N y este puede ser dividido en problemas de menor tamaño pero cuya solución es similar a la del problema original, conocidas las soluciones de estos problemas de tamaño menor, podemos obtener la solución al problema de tamaño N original a partir de estas soluciones más pequeñas. Los casos en que el problema es tan pequeño que su solución es trivial se conocen como casos base.

La iteración, por otro lado, se define iteración el acto y consecuencia de repetir un proceso con la intención de lograr un objetivo. La recursividdad es un caso especial de iteración.

Visto que ambos conceptos son similares, ¿por qué surge esta necesidad de toma de decisiones en cuanto a usar uno u otro tipo de algoritmo?

Como suele ocurrir en programación, existen varias formas y algoritmos aplicables para lograr un mismo objetivo. Para que podamos comprender esto, ilustraremos con un ejemplo sencillo las diferencias entre la técnica recursiva y la iterativa para resolver un mismo problema: obtener el factorial de un número.

El enunciado es simple: el factorial de un número resulta de la multiplicación de dicho número por todos los números naturales que haya entre él y 1, siendo el factorial de 0 y 1 igual a 1. Dicho recursivamente: el factorial de un número resulta de multiplicar dicho número por el factorial de su anterior.

n! = n * (n-1)!

Solución del factorial de un número por el método iterativo

Si nunca has programado un método recursivo o simplemente no tienes la “idea feliz”, probablemente la primera solución que te venga a la cabeza para resolver esto sea la iterativa: conocido el número del que se desea obtener el factorial, comprobaremos si dicho número es 0 o 1 (en cuyo caso devolveremos 1) y, en caso contrario, almacenaremos en una variable los resultados parciales de las operaciones de multiplicación. A esta solución se puede llegar fácilmente con un bucle for o while sencillo. Por ejemplo, para calcular el factorial de 9:

public class FactorialIterativo{
   public static void main(String[]args){

      int n=9; //Número cuyo factorial queremos obtener
      int result=1 //Variable que almacenará los resultados parciales y final

      if(n<=1) //Se comprueba si el número es o no 0 o 1.
         System.out.println("1");

      for(int i=2; i<=n; i++) //Iteraremos hasta llegar al número n, multiplicando y almacenando en la variable result el resultado de multiplicar el resultado acumulado por el siguiente.
         result=result*i;

      System.out.println(res); //Al salir del bucle, la variable result contiene el valor del factorial de 9
   }

Solución Solución del factorial de un número por el método recursivo

Si tienes algo más de experiencia en programación o estás estudiando recursividad, probablemente asome por tu cabeza esta segunda solución. Recursivamente, se irán haciendo llamadas al mismo método hasta que se alcance un caso base, momento en que todas las llamadas previas comenzarán a solucionarse recogiendo las soluciones obtenidas del resto de llamadas que tiene por debajo en el árbol recursivo. El método para esta solución recursiva podría ser el siguiente:

public static void factorialRecursivo(int n){
	if (n<=1){ //Comprobamos si estamos en el caso base
		return 1; //En cuyo caso devolveremos 1
	}else{
		int solParcial = factorialRecursivo(n-1); //Almacenamos la solución parcial. Aquí se realiza  la llamada recursiva al método que se está ejecutando con el valor n-1.
		int solucion = solParcial * n; //Calculamos la solución final
		return solucion; //Y la devolvemos
	}

}

Como puedes ver, este método se llama a si mismo durante su ejecución. Esta llamada se realizará hasta que n tenga un valor con el que se llegue al caso base (en este caso, cuando n=1). Pero, ¿qué pasa si nunca se alcanza un caso base? Pues que tendremos una recursión infinita y nuestro ordenado acabará quedándose sin memoria. Hay que tener mucho cuidado cuando programemos soluciones recursivas a la hora de establecer los casos base correctamente para evitar este tipo de situaciones.

Si aún no comprendéis muy bien cómo funciona la recursividad, tal vez os ayude esta herramienta desarrollada por la Universidad de San Francisco que muestra gráficamente la ejecución de este mismo algoritmo. Al ser tan visual el concepto es más fácil de aprender (a mí personalmente me ayudó mucho).

Entonces, ¿qué utilizo?

Podemos ver que ambos métodos son muy similares. La diferencia entre ambas implementaciones radica más en un aspecto físico/de hardware que en metodologías o skills de programación: el uso de la memoria.

Cuando programamos recursivamente, todos los resultados parciales se van almacenando en memoria en tiempo de ejecución. Si nuestro árbol recursivo se expande en demasía, es probable que nuestra memoria acabe por agotarse.

Por otro lado, la complejidad para encontrar una solución iterativa a veces es muy elevada. Sobre todo a la hora de implementar fórmulas o soluciones matemáticas (muchas de las cuales se apoyan en la recursividad para definirse), es más fácil alcanzar una solución recursiva que iterativa.

A la hora de utilizar la recursividad, es posible que se produzca redundancia, es decir, que se resuelva el mismo problema en más de una ocasión. Es aquí donde entran en juego técnicas como el branch and bound que intentan reducir el número de casos recursivos mediante la predicción de soluciones no válidas antes de alcanzar el nivel del árbol que las devuelve (pero estas técnicas quedan fuera del alcance de este post. Si tienes interés, no dudes en comentar para que hagamos un post hablando de algoritmos y técnicas de programación algo más avanzadas).

Conclusiones

En definitiva, no hay una norma establecida acerca de cuándo implementar una solución recursiva y cuándo una iterativa. Existen varios factores que ya hemos mencionado a lo largo del artículo y que hay que tener en cuenta respecto a la recursividad, que se resumen en:

  • La recursividad consume mucha memoria y tiempo de ejecución.
  • La recursividad puede dar lugar a la redundancia (resolver el mismo problema más de una vez)
  • A veces es más sencillo encontrar una solución recursiva que una iterativa

Personalmente, aconsejaría que siempre que se pueda utilizar una solución iterativa sea esta la que implementemos. Así no tendremos que preocuparnos más de la cuenta de las limitaciones físicas de la máquina en que se ejecute nuestro código. Este es un aspecto a tener en cuenta especialmente en los concursos de programación competitiva de los que os hablábamos hace unas semanas, en los que los problemas tienen límites marcados de tiempo de ejecución y memoria.

Cabe apuntar que existen paradigmas de programación cuya base es la recursividad, como ocurre con los lenguajes de programación lógica como pueden ser Prolog o Haskell, en los que prácticamente todo se consigue empleando métodos recursivos.

Esperamos haber arrojado algo de luz sobre esta cuestión que a todo programador le asalta alguna vez a lo largo de su carrera, especialmente cuando se está iniciando en ella. Si tras leer el post tienes alguna duda o simplemente no estás de acuerdo con lo aquí expuesto, no dudes en comentar, siempre está bien escuchar opiniones contrarias a la tuya (siempre que estén bien argumentadas, claro).