Dentro del manual de iniciación a la programación que venimos publicando en DesarrolloWeb.com, vamos a ver una de las primeras cosas que enseñan en la creación de algoritmos: la recursividad.

Qué es la recursividad

Como definición la RAE indica de la recursividad lo siguiente: Que se contiene a sí mismo un número indefinido de veces. Como proceso recursivo anota que se aplica de nuevo al resultado de haberlo aplicado previamente. Estas definiciones se acercan bastante a las que manejamos en el mundo de la programación, pero con algunos matices. Para nosotros la recurividad es un proceso que se implementa en base a la la aplicación de él mismo.

Ya en lo que respecta a las funciones recursivas, podemos decir que son aquellas que se llaman a si mismas para resolverse. Dicho de otra manera, una función recursiva se resuelve con una llamada a si misma cambiando el valor de un parámetro en la llamada a la función. A través de las sucesivas llamadas recursivas a la función, se van obteniendo valores que, computados, sirven para obtener el valor de la función llamada originalmente.

Caso base en las funciones recursivas

Para que se pueda aplicar correctamente la recursividad necesitamos que exista un caso base, en la que la resolución del problema sea inmediata y no requiera invocarse de nuevo el proceso.

Dicho de otra forma, el proceso de llamadas recursivas siempre tiene que acabar en una llamada a la función que se resuelve de manera directa, sin necesidad de llamar de nuevo a la función recursiva. Esto será siempre necesario, para que llegue un momento que se corten las llamadas reiterativas a la función y no se entre en un bucle infinito de invocaciones.

Ejemplo típico de recursividad

Quizás en la teoría cueste más ver lo que es una función recursiva que por la práctica. Un ejemplo típico de recursividad sería la función factorial. El factorial es una función matemática que se resuelve multiplicando ese número por todos los números naturales que hay entre él y 1.

Por ejemplo, factorial de 4 es igual a 4 * 3 * 2 * 1. Si nos fijamos, para el ejemplo de factorial de 4 (factorial se expresa matemáticamente con un signo de admiración hacia abajo, como 4!), se puede resolver como 4 * 3! (4 * factorial de 3). Es decir, podemos calcular el factorial de un número multiplicando ese número por factorial de ese número menos 1.

n! = n * (n-1)!

En el caso de la función factorial, tenemos el caso básico que factorial de 1 es igual a 1. Así que lo podremos utilizar como punto de ruptura o caso base de las llamadas recursivas.

Así pues, vamos a realizar la codificación de la función recursiva factorial. Primero veamos un pseudocódigo:

funcion factorial(n)
   si n=1 entonces
      factorial = 1
   sino
      factorial = n * factorial(n-1)
fin funcion

Ahora veamos cómo se implementaría esta función con el lenguaje de programación Javascript:

function factorial(n) {
   if(n == 1) {
      return 1
   } else { 
      return n * factorial(n-1)
   }
}

Recursividad aplicada a problemas comunes

En general es posible aplicar recursividad a una muy variada gama de algoritmos. El factorial que acabamos de ver es un ejemplo de libro, pero también podríamos definir un proceso recursivo en algo tan sencillo como la suma.

Para ello vamos a estipular que cualquier número sumado a otro es la suma del primer número mas 1, mas el segundo número decrementado en 1.

x + y = x + 1 + (y - 1)

Además, como caso base vamos a decir que cualquier número sumado a cero es ese mismo número.

x + 0 = x

Ahora podríamos definir la suma con esta función Javascript. Examíname con detenimiento y toma tus propias conclusiones:

function sumaRecursiva(x, y) {
  if(y == 0) {
    return x
  } else {
    return sumaRecursiva(x + 1, y - 1)
  }
}

Ahora vamos a hacer otro ejercicio matemático un poco más complejo que la suma para seguir jugando un poco con esto de las definiciones recursivas. Queremos definir el proceso de potenciación de manera recursiva, ya sabes, la base elevada a un exponente.

En matemáticas podríamos expresar la potenciación de esta manera:

potencia = base * base elevado a (exponente - 1)

En este caso podemos considerar el caso base como que toda base elevada al exponente 0 es equivalente a 1.

base elevado a 0 = 1

Con estas ideas claras podemos definir la operación matemática de potencia como una función recursiva con este código Javascript:

function potenciacionRecursiva(base, exponente) {
  if(exponente == 0) {
    return 1
  } else {
    return base * potenciacionRecursiva(base, exponente - 1)
  }
}

Conclusión sobre recursividad

Como se puede ver, la recursividad no representa ninguna dificultad y de hecho es una herramienta muy útil para programación de algoritmos. En desarrolloWeb hemos publicado en diversos lugares funciones que trabajan de forma recursiva. Es verdad que en un principio puede resultar dificil de entender o de saber cuando utilizar, pero cuando dominemos el concepto veremos que es una manera excelente de resolver problemas con cualquier lenguaje de programación.

Hay muchos algoritmos que sólo se resuelven con recursividad, o al menos cuya resolución más directa y elegante está basada en realizar funciones recursivas, que se llamen a si mismas para obtener el resultado final. Por ejemplo el recorrido de diversas estructuras de datos, como las de tipo árbol, siempre se acostumbran a realizar de manera recursiva, para poder estar seguros de que pasamos por todas las ramas del árbol.