Funciones recursivas. Recursividad

  • Por
Explicamos qué es una función recursiva y cómo implementar recursividad o hacer funciones recursivas en un lenguaje de programación.
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.

Referencia: Doy algunas direcciones de artículos de DesarrolloWeb.com que resuelven problemas creando funciones recursivas:

Autor

Miguel Angel Alvarez

Miguel es fundador de DesarrolloWeb.com y la plataforma de formación online EscuelaIT. Comenzó en el mundo del desarrollo web en el año 1997, transformando su hobby en su trabajo.

Compartir

Comentarios

Ronald Aybar

25/8/2016
El comportamiento de la recursividad no es igual o otros lenguajes??
Buenas noches, te hago la pregunta porque he conseguido una función recursiva para hacer combinacion de numeros ejemplo: [2,13,4] esta combinacion de numero genera 6 combinaciones en distintas posiciones, pero la funcion que he conseguido usa la palabra return y deja de funcionar la recursividad como normalmente trabaja en otros lenguajes. Te dejo el codigo para que lo veas


Array.prototype.subList=function(init, end){
var n_array=new Array();
for(i in this){
if(i>=init && i<end){
n_array.push(this[i]);
}
}
return n_array;
};
var a_partial=[],g_out=[], a_evaluar=[2,7,9,11];
function generar_combinacion(a_source, a_partial, lc_out){//([2,7,9,11],[],[]):
if(a_source.length==0){
lc_out.push(a_partial);
return;
}
for(j=0;j<a_source.length;j++){
var new_partial=a_partial;
$.each(a_source.subList(j,j+1), function(i,e){ new_partial.push(e);});
var new_source=[];
if(j<(a_source.length+1)){
$.each(a_source.subList(j+1, a_source.length), function(i,e){ new_source.push(e);});
}
generar_combinacion(new_source, new_partial, lc_out);
}
}
generar_combinacion(a_evaluar, a_partial, g_out);

Si pudieras aclarar mi duda agradecido infinitamente.