A mi me gusta ver conceptos como estos explicados en código, por que así puedo entender las cosas mejor. Los ejemplo estan en JavaScript, solo abran Firebug o Dev Tools in chrome para experimentar.
Digamos que queres sumar los números desde el 1 al 10. Lo primero que se nos ocurre es hacer algo como
var sum = 0;
for(var i=0; i<=10; i++){
sum += i;
}
console.log(sum); // 55
Lo anterior se puede expresar muchas veces usando recursion, de la siguiente manera
var sum = function(n){
if(n === 0){
return 0;
}else{
return n + sum(--n);
}
};
Si llamas la función con n = 10
sum(10); // 55
...el proceso continua hasta encontrar n = 0, haciendo 'basicamente' esto
10 +
10 + 9
10 + 9 + 8
10 + 9 + 8 + 7
.....
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
Ahora, hay que mantener en cuenta lo que ~ menciono: recursion demanda bastante memoria por que guarda el 'estado' de cada objeto.
Por ejemplo,
sum(10000); // 50,005,000 todo azul
Pero
sum(100000); // Maximum call stack size exceeded
:-( ... en el ultimo caso mejor ocupa un bucle.
Nota: Esto es aliviado en ciertos lenguajes basados en lisp que han optimizado tail recursion y son stateless pero esto no viene al tema.
Ahora, todo esto suena muy teorico y nada que nos beneficie mucho en las tareas cotidianas. Por ejemplo mas de alguna ves hemos querido sumar todos los numeros en un array, un bucle adentro de una función es suficiente, pero adonde queda la diversion!? Pues si usamos recursion podemos implementar dicho algoritmo de la siguiente manera
var arrsum = function(arr, i){
if(i === -1){
return 0;
}else{
return arr[i] + arrsum(arr, --i);
}
};
Supongamos queremos sumar los elementos de
var arr = [1,2,3,4,5];
Solo llamamos la funcion asi:
arrsum(arr, 4); // 15
Hay muchas cosas que tener en cuenta como las implicaciones en el consumo de memoria, velocidad y que tan expresivo podes hacer el codigo. Pero para empezar solo debes de saber que la recurrencia no es nada mas que hacer una llamada a la misma funcion dentro de su declaracion y definir cuando queres que las recursive calls se detengan. Con esto podes imaginar la cantidad de algoritmos en los cuales podes implementarla.
Bonus
Esto puede ser un poco offtopic pero lo voy a dejar aqui de todos modos:
Para los que siguen leyendo, noten que en la funcion arrsum pasamos el indice del ultimo elemento, esto se puede aliviar usando ciertas tecnicas que nos permiten crear scopes, por ejemplo en JavaScript podemos hacer lo siguiente:
var superarrsum = function(arr){
return (function(arr, i){
return (i === -1)? 0 : arr[i] + arguments.callee(arr, --i);
}(arr, arr.length - 1));
};
Basicamente creamos un nivel en el que podemos automaticamente pasar el ultimo indice del array. Ahora solamente hacemos la llamada asi:
superarrsum([1,2,3,4,5,6,7,8,9,10]); // 55
Pero podemos hacer muchisimo mas ;-) Por ejemplo restar, multiplicar, dividir incluso hacer operaciones similares a los iterators de ruby.
Encuesta