Funciones recursivas. Recursividad

30/9/08 - 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.

Como definición general, podemos decir que una función recursiva es aquella que se llama a si misma 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.

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 invocar de nuevo la función. 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.

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 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)
}

Como se puede ver, la recursividad no representa ninguna dificultad y de hecho es una herramienta muy útil para programación de algoritmos. En desarrollo web .com hemos publicado en diversos lugares funciones que trabajan de forma recursiva. Entiendo 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.

Autoría, licencia y acciones sobre este artículo

Informe de Miguel Angel Alvarez* Director de DesarrolloWeb.com URL: http://www.desarrolloweb.com Atención: Contenido exclusivo de DesarrolloWeb.com. No reproducir. Copyright. * Para consultas técnicas utilizar la lista de correo. Versión imprimible del artículo Enviar artículo por e-mail Publicar un comentario del artículo

Comentarios de los visitantes

Añadir un comentario del artículo Aun no hemos recibido comentarios de este artículo. Puedes ser el primero en enviar tu comentario.

  Ir arriba