Sv Community El Salvador
Soporte y Tecnología => Programación => C/C++ => Mensaje iniciado por: wilton milber en julio 08, 2011, 11:24:03 am
-
Hola quisiera saber si la recursividad se puede usar en cualquier algoritmo o solo se puede usar en un determinado caso :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup:
-
Hola, parece q se olvidan en contestarle a la gente xD
La verdad da lástima que mucha gente en este foro sabe muchas cosas con respecto a progra, etc y aqui son fantasmas :D
entonces, tu punto era recursividad no? :thumbsup:
estás hablando de recursividad con modularidad vrdd? o "recursividad" en iteraciones?... :-/ esq "un determinado caso" no me dice mucho!!
-
recursividad se usa cuando necesitas evaluar usando el mismo set de operaciones.
Se usa en sistemas retroalimentados, por lo general la respuesta de una operacion es el argumento de la siguiente operacion y la operacion a realizar es la misma.
yo usaba recursividad en resoluciones matemáticas, en series aritméticas
por ejemplo:
(http://www.regentsprep.org/Regents/math/algtrig/ATP3/recursivepattern.jpg) (http://www.regentsprep.org/Regents/math/algtrig/ATP3/recursivepattern2.jpg)
-
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.
-
Puu!! me toparon el disco :thumbsup: :sur: :sur: buena... creo q ya hay suficiente info para wilton milber