Menú de navegaciónMenú
Categorías

La mejor forma de Aprender Programación online y en español www.campusmvp.es

?id=6b958be0-1794-4ed1-bf5f-1b241f199f6d

¿Qué es la recursividad o recursión? - Un ejemplo con JavaScript

Recursividad-Portada

Un concepto que siempre le cuesta bastante a los programadores que están empezando es el de recursión o recursividad (se puede decir de las dos maneras).

Aunque es un concepto que puede llegar a ser muy complejo, en esencia es muy sencillo:

La recursividad consiste en funciones que se llaman a sí mismas, evitando el uso de bucles y otros iteradores.

Uno ejemplo fácil de ver y que se usa a menudo es el cálculo del factorial de un número entero. El factorial de un número se define como ese número multiplicado por el anterior, éste por el anterior, y así sucesivamente hasta llegar a 1. Así, por ejemplo, el factorial del número 5 sería: 5x4x3x2x1 = 120.

Tomando el factorial como base para un ejemplo, ¿cómo podemos crear una función que calcule el factorial de un número? Bueno, existen multitud de formas. La más obvia quizá sería simplemente usar un bucle determinado para hacerlo, algo así en JavaScript:

function factorial(n){
  var res = 1;
  for(var i=n; i>=1; i--){
    res = res * i;
  }
  return res;
}

Sin embargo hay otra forma de hacerlo sin necesidad de usar ninguna estructura de bucle que es mediante recursividad. Esta versión de la función hace exactamente lo mismo, pero es más corta, más simple y más elegante:

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

Aquí lo que se hace es que la función se llama a sí misma (eso es recursividad), y deja de llamarse cuando se cumple la condición de parada: en este caso que el argumento sea menor o igual que 1 (que es lo que hay en el condicional).

Si analizamos su ejecución paso a paso veríamos lo que está representado por la siguiente animación:

Es decir, cuando llamamos a la primera función, ésta se llama a sí misma pero pasándole un número menos y así sucesivamente hasta llegar a la última (la que recibe un 1 y por lo tanto deja de hacer más llamadas). En el momento en el que alguna de ellas empieza a devolver valores "hacia atrás", regresa la llamada a cada una de ellas, los valores devueltos se van multiplicando por el parámetro original en cada una de ellas, hasta llegar arriba del todo en el que la primera llamada devuelve el valor buscado.

Es un concepto que cuesta un poco entender pero que es muy poderoso.

Ventajas e inconvenientes

¿Ganamos algo al utilizar recursión en lugar de bucles/iteradores para casos como este?

En este caso concreto del cálculo factorial no, y de hecho es una forma más lenta de hacerlo y ocupa más memoria. Esto no es preocupante en la realidad, pero conviene saberlo. Lo del factorial es solo una forma de explicarlo con un ejemplo sencillo y que sea fácil de entender.

Pero entonces, si no ganamos nada en este caso ¿para qué sirve realmente la recursividad?

Pues para resolver ciertos problemas de manera elegante y eficiente.

El ejemplo típico sería el recorrer un árbol de elementos para hacer algo con todos ellos. Imagínate un sistema de archivos con carpetas y subcarpetas y archivos dentro de estas carpetas, o el árbol de elementos (DOM) de una página web donde unos elementos incluyen a su vez otros y no sabes cuántos hay en cada uno. En este tipo de situaciones la manera más eficiente de hacer una función que recorra todos los elementos es mediante recursión. Es decir, creas una función que recorra todos los elementos hijo del nodo que le pases y que se llame a sí misma para hacer lo mismo con los sub-nodos que haya. En el caso del sistema de archivos le pasarías una carpeta y se llamaría a sí misma por cada subcarpeta que hubiese, y así sucesivamente con todas las demás. Con una sola llamada inicial recorrerá automáticamente toda la estructura del sistema de archivos.

Con eso, y sin necesidad de complicarte, de repente tienes una función muy poderosa capaz de enumerar cualquier estructura arbitraria por compleja que sea.

Ahí es donde se ve el verdadero poder de la recursividad, aunque hay aplicaciones más potentes y más complejas todavía.

Detalles a tener en cuenta

Otra cosa importante a tener en cuenta es que, cada vez que se hace una llamada a una función desde otra función (aunque sea a sí misma), se crea una nueva entrada en la pila de llamadas del intérprete. Ésta tiene un espacio limitado por lo que puede llegar un punto en el que si se hacen demasiadas se sature y se produzca un error. A este error se le denomina "Desbordamiento de pila" o "Stack Overflow". Ahora ya sabes de donde viene el nombre del famoso sitio para dudas de programadores sin el que la programación moderna no sería posible ;-)

Además, hay que tener mucho cuidado con la condición de parada. Ésta se refiere a la condición que se debe comprobar para determinar que ya no se harán más llamadas a la función. Es en ese momento en el que empiezan a devolverse los valores hacia "arriba", retornando a la llamada original.

Si no tienes la condición de parada controlada pueden pasar varias cosas (todas malas), como por ejemplo:

  • Que se sature la pila y se produzca un desbordamiento
  • Que ocupes cada vez más memoria
  • Que se produzcan desbordamientos de variables al ir acumulando resultados
  • En JavaScript, que el navegador -al cabo de unos segundos- avise al usuario de que hay un script descontrolado y que lo detenga.
  • ....

Así que es crucial controlar la condición de parada.

Por ejemplo, en el caso de nuestro cálculo factorial en JavaScript, como esta función enseguida crea números enormes, es bueno que lo limitemos de algún modo. En este caso sencillo del factorial, por ejemplo podríamos limitar el cálculo al número 100 (¡100 factorial es enorme!, un valor seguido de cientos de ceros) y así limitamos el número de llamadas en la pila a 100 como máximo también. Además, ya que estamos, le añadimos soporte para que calcule factoriales de números negativos.

Para ello podemos tener esta versión "definitiva" de la función recursiva:

function factorial(n) {
    n = parseInt(n);    //Trato de obtener un entero
    var signo = Math.sign(n);  //Averiguo su signo
    n = Math.abs(n);    //Calculo el factorial sobre el valor absoluto (positivo)

    if (n>=100)
    throw "El número es demasiado grande;";
    
    //Cálculo del factorial
    if (isNaN(n) || n<=0) return 1;
    return signo*n* factorial(n-1);    //Se devuelve el signo (solo en la primera llamada habrá signo negativo)
}

Que usa igualmente recursión, pero le hemos metido otro tipo de controles para hacerla más robusta.

Como nota simpática sobre la recursión: si buscas en Google (en inglés) la palabra "Recursion" (que es recursividad en inglés) te dice que si querías decir "Recursion" (o sea, lo mismo), en un guiño a los programadores que saben qué significa esto Open-mouthed smile:

Recursion-Google

¡Espero que te resulte útil!

Fecha de publicación:
José Manuel Alarcón Fundador de campusMVP, es ingeniero industrial y especialista en consultoría de empresa. Ha escrito diversos libros, habiendo publicado hasta la fecha cientos de artículos sobre informática e ingeniería en publicaciones especializadas. Microsoft lo ha reconocido como MVP (Most Valuable Professional) en desarrollo web desde el año 2004 hasta la actualidad. Puedes seguirlo en Twitter en @jm_alarcon o leer sus blog técnico o personal. Ver todos los posts de José Manuel Alarcón

¿Te vas a perder los mejores trucos de programación?

Únete a miles de desarrolladores que ya reciben cada mes nuestro boletí­n por email. No te pierdas los mejores trucos, noticias y frikadas.

Enviamos poco, pero bueno. Palabra de desarrollador.

Suscríbete aquí­

Sí­guenos también en:

Telegram LinkedIn YouTube
La mejor formación online para desarrolladores como tú

Comentarios (4) -

Hugo Moragues
Hugo Moragues

Me gustaría hacer un apunte acerca de la función factorial() que habéis definido en el artículo: Esta implementación es correcta siempre que no se le cambie el nombre a la función. Pero existe un estrecho acoplamiento entre la ejecución de la función y el propio nombre 'factorial'. Siempre que el nombre de la función no varíe, todo irá perfecto... Ahora bien, teniendo la función factorial() definida, si añadimos esto:

var miFactorial = factorial;
factorial = function() { return 0;};
console.log(factorial(5)); // 0, ok, es lógico, no?
console.log(miFactorial(5)); // 0, WTF!?

Esto ocurre por la última línea de la función:

return signo*n* factorial(n-1);

Lo que ocurre es que la variable factorial (los nombres de las funciones en ECMAScript son sencillamente variables) es reasignada a una función que devuelve 0, pero en la última línea de miFactorial, seguimos llamando a factorial(), con lo que la ejecución siempre nos devolverá 0 (signo*n*0 = 0).
En lugar de llamar a factorial en esa línea, es más correcto emplear la propiedad callee del objeto arguments (callee es un puntero a la función a la que pertenece arguments), entonces la línea anterior quedaría así:

return signo*n*arguments.callee(n-1);

Sé que lo que comento no tiene demasiado que ver con el objetivo del artículo, y no quiero que se entienda como una crítica, simplemente es una corrección que me parece interesante, sobre todo por cómo se comporta Javascript cuando implementa algoritmos como el del factorial. Además, callee me parece interesante y a veces imprescindible cuando se tratan problemas de recursión en JS.

Saludos!

Responder

José Manuel Alarcón
José Manuel Alarcón

Hola Hugo:

Antes de nada: gracias por comentar.

En realidad el uso de callee está desaconsejado por varios motivos. El primero es que si estamos utilizando el modo estricto (www.campusmvp.es/.../...e-es-y-para-que-sirve.aspx), cosa que deberíamos casi siempre, callee no funciona. Y segundo porque el uso de callee impide las optimizaciones en tiempo de ejecución que hacen los motores de JavaScript por debajo.

Como tú bien dices el objeto del artículo no era este, sino tratar de explicar a los principiantes el concepto de recursión. Pero lo que comentas es interesante, así que aprovecho y explico mi punto de vista.

Antes de todos modos me gustaría hacer un inciso y explicar otra cosa previa, ya que lo que comentas de que "los nombres de las funciones en ECMAScript son sencillamente variables", no es del todo correcto. Una función es un objeto, con las mismas capacidades que cualquier otro objeto del lenguaje, y como tal lo puedes asignar a una o varias variables. En el caso de las funciones globales lo que ocurre es que se definen como métodos del objeto global, que en el caso del navegador es la ventana (el objeto window, pero no siempre tiene que ser así en otros entornos: www.jasoft.org/.../...-Windows-Scripting-Host.aspx). Cuando escribes "factorial = function() {return 0;  }" en realidad lo que haces es reasignar el valor del método "factorial" del objeto window. El efecto es el mismo, pero el concepto es diferente.

Dicho esto y volviendo al tema del cambio de nombre... En efecto, si cambiamos el nombre de la función en algún momento (algo que debiéramos hacer refactorizando y así no pasan estas cosas) o la redefinimos y es una función global, tendríamos el problema que comentas. Pero generalmente esto se puede evitar simplemente definiendo la función en un ámbito donde no pueda ser modificada por error (usando el patrón módulo, por ejemlo).

También podemos evitarlo definiendo la función con una expresión function CON NOMBRE. Es decir, en vez de darle un nombre sin más o asignar la función a una variable (que es CASI equivalente, ver: www.jasoft.org/.../...s-anonimas-y-con-nombre.aspx) de este modo:

var factorial = function(n) {
    if (n<=1) return 1;
    return n* factorial(n-1);
}

usamos esto:

var factorial = function fact(n) {
    if (n<=1) return 1;
    return n* fact(n-1);
}

Ahora aunque hagas esto que proponías:

var miFactorial = factorial;
factorial = function() { return 0;};

Al hacer:

console.log(miFactorial(5));

verás el resultado correcto.

Las expresiones de función con nombre te dan esta flexibilidad. Dentro de la función siempre podrás hacer referencia a la función original que estás definiendo (como en una clausura) y da igual desde dónde la estés llamando aunque la hayas reasignado. Además ese nombre (fact en nuestro caso) no existe fuera de la definición y no poluciona el espacio global de nombres ni tampoco puedes tocarlo en modo alguno, por lo que la función queda autocontenida y protegida ante eso que comentas, y mientras haya una referencia a la misma en algún lado, en cualquier variable, podrás utilizarla.

Nuevamente gracias por comentar, pues los comentarios constructivos muchas veces dan para desarrollos interesantes, como ha sido el caso :-)

Saludos!

Responder

Hugo Moragues
Hugo Moragues

Hola José Manuel,

Muchísimas gracias por tu respuesta, con lo que comentas he acabado de entender algunos conceptos que ahora veo no tenía del todo claros :D

Muy enriquecedor, tanto el post como tu comentario!

Responder

Gracias por esta explicación tan clara!

Responder

Agregar comentario

Los datos anteriores se utilizarán exclusivamente para permitirte hacer el comentario y, si lo seleccionas, notificarte de nuevos comentarios en este artículo, pero no se procesarán ni se utilizarán para ningún otro propósito. Lee nuestra política de privacidad.