Encuesta

cual es mejor??

recursividad buena
1 (50%)
recursivida mala
0 (0%)
ambas buenas
1 (50%)

Total de votos: 2

Autor Tema: recursividad  (Leído 4637 veces)

0 Usuarios y 1 Visitante están viendo este tema.

wilton milber

  • Visitante
  • Trade Count: (0)
recursividad
« : 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:
« Última Modificación: julio 08, 2011, 11:26:44 am por wilton milber »

Desconectado Non Servium

  • Trade Count: (0)
  • Sv Member
  • ***
  • Thank You
  • -Given: 6
  • -Receive: 39
  • Mensajes: 426
  • Ilix Punx :)
Re: recursividad
« Respuesta #1 : julio 18, 2011, 04:42:19 pm »
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!!
♫ Condenados a perder la libertad! Por no acatar las leyes que les asignaron. ♪ ♫
Decididos, decididos a emprender! Un camino largo y duro por no ser esclavos ♫


Watch

Desconectado Jaru

  • Trade Count: (21)
  • The Communiter-
  • *
  • Thank You
  • -Given: 782
  • -Receive: 1555
  • Mensajes: 13248
  • -text
Re: recursividad
« Respuesta #2 : julio 18, 2011, 05:28:40 pm »
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:
Follow members gave a thank to your post:
N/A

Desconectado ~

  • Trade Count: (0)
  • The Communiter-
  • *
  • Thank You
  • -Given: 0
  • -Receive: 156
  • Mensajes: 1408
    • Ciencia de Computación, OSes y Herramientas
Re: recursividad
« Respuesta #3 : julio 18, 2011, 06:54:19 pm »
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:

Sí, se puede usar en cualquier algoritmo, puede servir en ciertos casos en los que se desea que la estructura/cantidad de datos así como su manejo/manipulación sea totalmente dinámica, o si se necesita manejar datos dinámicos en cantidad y estructura, aunque siempre involucrando otros algoritmos propios de esos datos; aunque no siempre es conveniente ni práctico. Es especialmente útil y aplicable en algoritmos que usan estructuras o instrucciones/tareas repetitivas, pero no cualquier tarea repetitiva sino que un tipo de tarea repetitiva para la que no se conoce un límite de suboperaciones bien definido. Un buen ejemplo es recorrer recurrentemente un árbol de carpetas y subcarpetas para buscar, eliminar, mover, renombrar, etc... todo lo que hacen los exploradores de carpetas.

Hay muchos otros algoritmos, más simples y más complejos que usan recurrencia, pero la idea siempre es superar y lograr manejar un número irregular o no bien conocido de ramificaciones de una tarea, de la forma más eficiente y estable posible.

Se puede pensar en la recurrencia como una técnica que permite hacer "microcopias" de una subrutina, programa, etc.

La forma más simple de recurrencia es hacer que una función se llame a sí misma; pero en muchas ocasiones, si realmente no es necesario eso, un simple pero efectivo bucle puede ser preferible. También se puede lograr el efecto de recurrencia usando datos globales con una subrutina que no se llame a sí misma pero se llame repetidas veces en un bucle, procesando o manipulando más los datos o más datos en cada pasada, o deteniéndose (esta variedad puede aliviar la carga de la pila porque permite descartar copias locales de variables y estado del programa que en su mayor parte presumiblemente ya no importan y sería preferible simplemente descartar al regresar de la subrutina antes de volver a llamarla, para ahorrar esa cantidad de datos, que de forma recurrente y anidada puede ser considerable). Cada técnica de recurrencia o repetitividad con bucles tiene diferentes aplicaciones, y cada una es más conveniente y natural de codificar en unos casos, y menos efectivo y más difícil de codificar en otros.

En un programa, estructuras de código, como los bucles y las subrutinas no se pueden multiplicar dinámicamente como sí es el caso de la memoria dinámica.

Pero existe algo llamado recurrencia que tiene el mismo efecto que multiplicar los bucles y el código dinámicamente, especialmente el contenido en subrutinas, según lo necesiten los datos, especialmente datos "anidados" que forman estructuras de árboles/subdependencias para los que no se conozca de antemano el número de iteraciones/repeticiones de bucles requeridas para cada una de las "ramas" y que por lo general tengan "sub-ramificaciones" de datos con números diferentes de iteraciones requeridas en bucles, guiándose por decisiones bien pensadas para llamar una rutina dentro de sí misma o detener la cadena de llamadas. Esa es la aplicación y origen básico de la recursividad.

A pesar de eso, la recurrencia necesita un cuidado especial en ser manejada, porque a cambio de los beneficios que ofrece, demanda una gran cantidad de memoria (para la pila, para reservar más espacio para las variables de una nueva instancia de la función/funciones recurrente/s, etc.) cada vez que se llama a sí misma una función, y entre mayor sea la anidación de los datos. También puede causar bucles infinitos si las condiciones de recurrencia no están bien pensadas o si hay partes compartidas de un programa con errores de acceso simultáneo; y ambas son posibilidades que hay que evaluar y poner a prueba en un programa recurrente para dividir el trabajo en partes que demanden menos anidación, después de determinar mejores decisiones de recursividad, o simplemente y de ser posible, aumentando la memoria disponible para el programa (y la pila del programa).

___________________________

Sobre la pila: esta es simple y básicamente un área temporal de datos y memoria que el programa usa cada vez que llama una rutina y reserva memoria para sus variables locales, para guardar el estado del resto del programa para preservarlo antes de correr la subrutina y restaurarlo antes de regresar al código que llamó la subrutina, entre otras cosas.

Básicamente consumir todo el espacio de la pila es una situación que requiere reservar más espacio de pila de forma dinámica por el sistema operativo, o simplemente el programa falla y se cierra.

El problema con la recurrencia es que si hay suficiente anidación una y otra vez a una misma subrutina, la recurrencia es una operación especialmente demandante de espacio de pila y si no se tiene cuidado puede ser demasiado pesada para ser razonable y el programa simplemente falla después de que consume todo el espacio de pila que se le puede asignar.



Follow members gave a thank to your post:
« Última Modificación: julio 18, 2011, 07:31:13 pm por ~ »
Mi sitio web:
---- IP para archivo hosts (todos mis subdominios):
190.150.9.244 archefire.org

Desconectado JaiMe

  • Global Moderator
  • Trade Count: (0)
  • The Communiter-
  • *
  • Thank You
  • -Given: 43
  • -Receive: 413
  • Mensajes: 1485
  • λ | h+
Re: recursividad
« Respuesta #4 : julio 19, 2011, 02:50:05 am »
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

Código: [Seleccionar]
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

Código: [Seleccionar]
var sum = function(n){
     if(n === 0){
         return 0;
     }else{                   
         return n + sum(--n);
     }
};


Si llamas la función con n = 10

Código: [Seleccionar]
sum(10);      // 55
...el proceso continua hasta encontrar n = 0, haciendo 'basicamente' esto
Código: [Seleccionar]
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,

Código: [Seleccionar]
sum(10000);           // 50,005,000    todo azul

Pero

Código: [Seleccionar]
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

Código: [Seleccionar]
var arrsum = function(arr, i){
  if(i === -1){
    return 0;
  }else{
    return arr[i] + arrsum(arr, --i);
  }
};

Supongamos queremos sumar los elementos de
Código: [Seleccionar]
var arr = [1,2,3,4,5];
Solo llamamos la funcion asi:

Código: [Seleccionar]
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:

Código: [Seleccionar]
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:

Código: [Seleccionar]
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.
"Unless you try to do something beyond what you have already mastered, you will never grow."
― Ralph Waldo Emerson

Desconectado ~

  • Trade Count: (0)
  • The Communiter-
  • *
  • Thank You
  • -Given: 0
  • -Receive: 156
  • Mensajes: 1408
    • Ciencia de Computación, OSes y Herramientas
Re: recursividad
« Respuesta #5 : julio 19, 2011, 11:34:45 am »
Este podría ser una versión más eficiente en memoria del último ejemplo anterior, pasando un puntero a un objeto al estilo de C en lugar de una copia entera del arreglo. Más abajo he puesto más explicaciones.

Código: [Seleccionar]
javascript:

var miarreglo=new Object();
    miarreglo.arr=new Array(1,2,3,4,5,6,7,8,9,10);
    miarreglo.pos=new Number(-1);

var arrr = function(arr_ptr)
{
  arr_ptr.pos++;
   return (arr_ptr.pos >= arr_ptr.arr.length)? 0 : arr_ptr.arr[arr_ptr.pos] + arguments.callee(arr_ptr);
};

alert(arrr(miarreglo));

void(0);




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

Código: [Seleccionar]
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

Código: [Seleccionar]
var sum = function(n){
     if(n === 0){
         return 0;
     }else{                   
         return n + sum(--n);
     }
};


Si llamas la función con n = 10

Código: [Seleccionar]
sum(10);      // 55
...el proceso continua hasta encontrar n = 0, haciendo 'basicamente' esto
Código: [Seleccionar]
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,

Código: [Seleccionar]
sum(10000);           // 50,005,000    todo azul

Pero

Código: [Seleccionar]
sum(100000);         // Maximum call stack size exceeded

:-( ... en el ultimo caso mejor ocupa un bucle.


A eso me refiero, pero a veces hay problemas que legítimamente necesitan usar recurrencia (por ejemplo recorrer un servidor o red de servidores con billones de carpetas y subcarpetas y archivos) pero al mismo tiempo el tamaño de los datos es demasiado grande y no se puede usar simple recurrencia (¿Cómo mantener tanta recurrencia sin afectar la disponibilidad de recursos de memoria para otros procesos?) sino que hay que hacer cosas como lo que mencionaba de usar variables globales y no hacer que la función se llame a sí misma sino que llamarla repetitivamente dentro de un bucle y que trabaje sobre los datos externos. Así el consumo de la memoria se mantendría constante, lo que es una enorme ventaja porque ahora el programa solo estaría limitado por el tiempo de ejecución y podría correr incluso en sistemas de muy baja capacidad de memoria. La función en sí puede no ser recurrente, pero la operación sobre los datos sí es recurrente, con el beneficio de que ya no consume tanta memoria como el estereotipo común de función de llamada recurrente (las llamadas pueden ser recurrentes pero el efecto sobre los datos realmente no necesita de llamadas recurrentes para tener el mismo efecto final).

Para poner un ejemplo, en un sistema de 64 bits y teniendo una pila de 1 Mb (1048576 bytes) para el programa, en el mejor de los casos la función sum anterior podría llamarse hasta 1048592 veces porque el Megabyte se dividiría entre 16 porque cada vez que se llame recurrentemente la rutina se guardan 8 bytes en la pila, y el argumento numérico se llevaría otros 8 bytes.

La misma función usando un bucle podría manejar algo menos de 18446744073709552000 sumas (tomando en cuenta también el rápido incremento numérico en cada suma), que es el límite de un entero de 64 bits.

Para hacer lo mismo con recurrencia quizás se necesitaría una pila de 1,099,511,627,776 Megabytes, (18446744073709552000 números posibles / 16 bytes por llamada / 1048576 bytes del Megabyte, refiriéndonos al número crudo de sumas anidadas contínuas posibles).


Nota: Esto es aliviado en ciertos lenguajes basados en lisp que han optimizado tail recursion y son stateless pero esto no viene al tema.


Es posible que "globalice" los datos relevantes para no tener que acumular copias innecesariamente, que obviamente es una operación poco optimizada. Pero siempre y cuando haya llamadas a funciones al estilo de C/Java/Javascript, que necesiten una cadena de llamadas anidadas, ese es exactamente el caso.

O reutilizar el estado de la pila actual, que es equivalente porque sigue usando la misma área de datos sin extenderse más allá de forma acumulada.

Pero el hecho de que este tipo de recurrencia (tail recursion) reutilice el "marco de pila" (o sea el estado actual de la función actual en lugar de agregar una nueva instancia para mantener el consumo de la memoria de la pila constante en todo momento y que tiene un efecto equivalente a globalizar ese estado temporal) demuestra que esa es una optimización de un nivel relativamente bajo, pero que puede implementarse a mano en otros lenguajes que no dispongan de esta nativamente:

http://stackoverflow.com/questions/33923/what-is-tail-recursion

Como puede verse hay muchas formas de aproximarse al problema de implementar la recurrencia. Por definición la mejor recurrencia es la que más operaciones pueda llevar a cabo sin consumir la pila; y si es posible usar total o parcialmente un bucle para llevar a cabo una tarea de forma estable y elegante y más natural en su lugar, es preferible hacerlo.

Puede haber problemas en los que el "tail recursion" no se aplique adecuadamente.



Ahora, todo esto suena muy teorico y nada que nos beneficie mucho en las tareas cotidianas.


El que se menciona sí es un problema real propio de estos algoritmos "avanzados". El problema es que la recurrencia aparentemente nunca se pensó o es una solución natural para problemas "cotidianos". No puedo pensar en muchos algoritmos lineales, como operaciones aritméticas cualquiera de 0 a n que no pudieran implementarse más natural y adecuadamente usando bucles en lugar de recurrencia.

Codificar un algoritmo con diferentes métodos (recurrencia, "pseudorecurrencia" (recurrencia de operaciones sobre datos sin llamadas recurrentes), tail recursion, bucles) sirve enormemente para evaluar adecuadamente las diferencias reales entre las implementaciones, pero por lo general la implementación más efectiva y naturalmente codificable es la preferible, aunque depende de cada necesidad. No hay algoritmo ni forma absoluta que la recurrencia deba seguir siempre y cuando persiga y logre alcanzar un objetivo de forma útil.


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!?


La diversión podría estar en encontrar el método más eficiente y capaz de hacer operaciones con el menor esfuerzo razonable de programación. También cosas como por ejemplo, para recorrer secuencialmente los sectores de un disco duro de varios Terabytes no sería buena idea incrementar el número de sector con recurrencia; mientras que para recorrer los árboles binarios o subdirectorios de los que está formada la estructura de directorios sí tendría sentido usar un poco de recurrencia y un poco de bucles (depende del implementador cómo vaya a lograrlo).

Aunque puede ser divertido si se toma en cuenta que eso puede servir para evaluar y entender cómo se ve el código recurrente en el propio código de máquina en ensamblador que la máquina realmente va a tener que correr:


Citar
function sum_recur(/*qword n*/)
{
 //Si el número del parámetro es 0
 //regresamos devolviendo 0:
 ///
  if(!qword[$RSP+8])
  {
   $RAX=0;
   goto .ends;
  }

 //Gracias al IF anterior, en ensamblador
 //no se necesita un ELSE porque un bloque
 //de código con una condición IF inmediatamente
 //arriba de este y con el final de la función
 //inmediatamente abajo de este se comporta automáticamente
 //como un ELSE (esto también pasa en cualquier
 //otro lenguaje, de hecho):
 ///


 //Tomamos el parámetro n:
 ///
  $RCX=qword[$RSP+8];

 //Ahora le disminuimos 1 para obtener n-1:
 ///
  $RCX--;

 //Preservamos RAX antes de la recurrencia.
 //RAX *siempre* contiene el valor devuelto:
 ///
  push $RAX;

   //Pasamos el parámetro n-1:
   ///
    push $RCX;
   
   //Llamamos de forma recurrente:
   ///
     sum_recur(/*$RCX*/);

   //Descartamos el parámetro n-1:
   ///
    $RSP+=8;

   //El resultado lo ponemos en una variable
   //temporal en RBX:
   ///
    $RBX=$RAX;

 //Restauramos RAX después de la recurrencia.
 //RAX *siempre* contiene el valor del resultado:
 ///
  pop $RAX;


 //Acumulamos el resultado actual con el obtenido
 //con recurrencia:
 ///
  $RAX+=$RBX;
  $RAX+=qword[$RSP+8];


 .ends:
}


$RAX=0;
sum_recur(10);




El proceso recurrente resultante:


Citar

qword[$RSP+8]==10
$RAX=0
$RCX=?
$RBX=?
________________________________

LLAMAR(10)
________________________________


(10)qword[$RSP+8]==10
(10)$RCX=qword[$RSP+8]==10-1 === 9
(10)new qword[$RSP+8]==$RCX === 9
(10)guardar $RAX==0
(10)nueva llamada(9)


 (09)qword[$RSP+8]==9
 (09)$RCX=qword[$RSP+8]==9-1 === 8
 (09)new qword[$RSP+8]==$RCX === 8
 (09)guardar $RAX==0
 (09)nueva llamada(8)


  (08)qword[$RSP+8]==8
  (08)$RCX=qword[$RSP+8]==8-1 === 7
  (08)new qword[$RSP+8]==$RCX === 7
  (08)guardar $RAX==0
  (08)nueva llamada(7)


   (07)qword[$RSP+8]==7
   (07)$RCX=qword[$RSP+8]==7-1 === 6
   (07)new qword[$RSP+8]==$RCX === 6
   (07)guardar $RAX==0
   (07)nueva llamada(6)


    (06)qword[$RSP+8]==6
    (06)$RCX=qword[$RSP+8]==6-1 === 5
    (06)new qword[$RSP+8]==$RCX === 5
    (06)guardar $RAX==0
    (06)nueva llamada(5)


     (05)qword[$RSP+8]==5
     (05)$RCX=qword[$RSP+8]==5-1 === 4
     (05)new qword[$RSP+8]==$RCX === 4
     (05)guardar $RAX==0
     (05)nueva llamada(4)


      (04)qword[$RSP+8]==4
      (04)$RCX=qword[$RSP+8]==4-1 === 3
      (04)new qword[$RSP+8]==$RCX === 3
      (04)guardar $RAX==0
      (04)nueva llamada(3)


       (03)qword[$RSP+8]==3
       (03)$RCX=qword[$RSP+8]==3-1 === 2
       (03)new qword[$RSP+8]==$RCX === 2
       (03)guardar $RAX==0
       (03)nueva llamada(2)


        (02)qword[$RSP+8]==2
        (02)$RCX=qword[$RSP+8]==2-1 === 1
        (02)new qword[$RSP+8]==$RCX === 1
        (02)guardar $RAX==0
        (02)nueva llamada(1)


         (01)qword[$RSP+8]==1
         (01)$RCX=qword[$RSP+8]==1-1 === 0
         (01)new qword[$RSP+8]==$RCX === 0
         (01)guardar $RAX==0
         (01)nueva llamada(0)


          (00)qword[$RSP+8]==0
          (00)$RAX=0
          (00)return

         (01)descartar temp qword[$RSP+8]-1 === (0)
         (01)$RBX == $RAX === 0
         (01)restaurar $RAX == 0
         (01)$RAX+=$RBX+*qword[$RSP+8] === 0+ 0+1 === (1)
         (01)return

        (02)descartar temp qword[$RSP+8]-1 === 1
        (02)$RBX == $RAX === 1
        (02)restaurar $RAX == 0
        (02)$RAX+=$RBX+*qword[$RSP+8] === 0+ 1+2 === (3)
        (02)return

       (03)descartar temp qword[$RSP+8]-1 === 2
       (03)$RBX == $RAX === 3
       (03)restaurar $RAX == 0
       (03)$RAX+=$RBX+*qword[$RSP+8] === 0+ 3+3 === (6)
       (03)return

      (04)descartar temp qword[$RSP+8]-1 === 3
      (04)$RBX == $RAX === 6
      (04)restaurar $RAX == 0
      (04)$RAX+=$RBX+*qword[$RSP+8] === 0+ 6+4 === (10)
      (04)return

     (05)descartar temp qword[$RSP+8]-1 === 4
     (05)$RBX == $RAX === 10
     (05)restaurar $RAX == 0
     (05)$RAX+=$RBX+*qword[$RSP+8] === 0+ 10+5 === (15)
     (05)return

    (06)descartar temp qword[$RSP+8]-1 === 5
    (06)$RBX == $RAX === 15
    (06)restaurar $RAX == 0
    (06)$RAX+=$RBX+*qword[$RSP+8] === 0+ 15+6 === (21)
    (06)return

   (07)descartar temp qword[$RSP+8]-1 === 6
   (07)$RBX == $RAX === 21
   (07)restaurar $RAX == 0
   (07)$RAX+=$RBX+*qword[$RSP+8] === 0+ 21+7 === (28)
   (07)return

  (08)descartar temp qword[$RSP+8]-1 === 7
  (08)$RBX == $RAX === 28
  (08)restaurar $RAX == 0
  (08)$RAX+=$RBX+*qword[$RSP+8] === 0+ 28+8 === (36)
  (08)return

 (09)descartar temp qword[$RSP+8]-1 === 8
 (09)$RBX == $RAX === 36
 (09)restaurar $RAX == 0
 (09)$RAX+=$RBX+*qword[$RSP+8] === 0+ 36+9 === (45)
 (09)return

(10)descartar temp qword[$RSP+8]-1 === 9
(10)$RBX == $RAX === 45
(10)restaurar $RAX == 0
(10)$RAX+=$RBX+*qword[$RSP+8] === 0+ 45+10 === (55)



Comparado con un bucle, esto es dramáticamente más intensivo pudiendo evitarse. Ese es el efecto de las llamadas recurrentes. Como se puede ver cada llamada y cada operación PUSH en la pila con una llamada recurrente pura aumenta el consumo y disminuye la velocidad del programa en cada acceso de memoria, además de los accesos de las operaciones POP.


Código: [Seleccionar]
function sum(/*$RAX n*/)
{
  $RBX=$RAX;
  $RAX=0;

  while($RBX)
  {
   $RAX+=$RBX;
   $RBX--;
  }
}


El proceso lineal resultante:

Citar

$RAX=10
$RBX=10
_________________
$RAX=0

$RAX+=$RBX === 0+10 == (10)
$RBX-- == 10-1 === 9

$RAX+=$RBX === 10+9 == (19)
$RBX-- == 9-1 === 8

$RAX+=$RBX === 19+8 == (27)
$RBX-- == 8-1 === 7

$RAX+=$RBX === 27+7 == (34)
$RBX-- == 7-1 === 6

$RAX+=$RBX === 34+6 == (40)
$RBX-- == 6-1 === 5

$RAX+=$RBX === 40+5 == (45)
$RBX-- == 5-1 === 4

$RAX+=$RBX === 45+4 == (49)
$RBX-- == 4-1 === 3

$RAX+=$RBX === 49+3 == (52)
$RBX-- == 3-1 === 2

$RAX+=$RBX === 52+2 == (54)
$RBX-- == 2-1 === 1

$RAX+=$RBX === 54+1 == (55)
$RBX-- == 1-1 === 0






Se nota que este código es más simple/ligero al expandirse en la ejecución. Ya no se diga con la complejidad y las operaciones de memoria (lentas) adicionales que necesitaría un arreglo. Por eso es mejor minimizar la complejidad de la recurrencia en el mayor grado posible.


  Pues si usamos recursion podemos implementar dicho algoritmo de la siguiente manera

Código: [Seleccionar]
var arrsum = function(arr, i){
  if(i === -1){
    return 0;
  }else{
    return arr[i] + arrsum(arr, --i);
  }
};

Supongamos queremos sumar los elementos de
Código: [Seleccionar]
var arr = [1,2,3,4,5];
Solo llamamos la funcion asi:

Código: [Seleccionar]
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.


Como decía anteriormente, ese es el concepto básico de recurrencia, pero también puede existir recurrencia en la manipulación de los datos sin que haya necesariamente recurrencia de llamadas a un procedimiento.




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:

Código: [Seleccionar]
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:

Código: [Seleccionar]
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.



Para tratar de aliviar todavía más la memoria, se podría tratar de emular un puntero al estilo de C a un Object global, "envolviendo" un arreglo dentro de este objeto personalizado, y pasando la referencia al objeto en lugar del arreglo en sí. Así no se tendría que crear una copia entera del arreglo cada vez que se llama una función con ese tipo de recurrencia.

Si una implementación de Javascript está apropiadamente optimizada esto debería pasar una referencia al objeto (que ocupa poca memoria) en lugar de una copia temporal del objeto entero (que ocupa "mucha" memoria).

Lo siguiente solo es de copiar y pegar en la barra de direcciones de Firefox/Chrome o en la consola de desarrollo:


Código: [Seleccionar]
javascript:

var miarreglo=new Object();
    miarreglo.arr=new Array(1,2,3,4,5,6,7,8,9,10);
    miarreglo.pos=new Number(-1);

var arrr = function(arr_ptr)
{
  arr_ptr.pos++;
   return (arr_ptr.pos >= arr_ptr.arr.length)? 0 : arr_ptr.arr[arr_ptr.pos] + arguments.callee(arr_ptr);
};

alert(arrr(miarreglo));

void(0);


__________________________________________________________
Código con comentarios:

Citar
javascript:

/* Creamos una nueva referencia de objeto conteniendo  */
/* un arreglo y un número inicializado en -1 para      */
/* llevar a cabo correctamente la recurrencia de 0 a 9 */
/* en este caso */
/***/
var miarreglo=new Object();
    miarreglo.arr=new Array(1,2,3,4,5,6,7,8,9,10);
    miarreglo.pos=new Number(-1);



/* Función que suma arreglos.                                 */
/*                                                            */
/* Esta vez toma un puntero de objeto en lugar de un arreglo  */
/* directo para minimizar el consumo de memoria */
/***/
var arrr = function(arr_ptr)
{
 /* Sumamos 1 para avanzar al siguiente elemento recurrentemente:  */
 /***/
   arr_ptr.pos++;

 /* Evaluamos. Si vemos que ya sobrepasamos todos los elementos    */
 /* del arreglo, devolvemos 0 para romper la recurrencia y que el  */
 /* valor de 0 no altere la suma.                                  */
 /* Si todavía estamos dentro del límite de elementos del arreglo, */
 /* tenemos que hacer una llamada recurrente que obtendrá el       */
 /* siguiente valor para sumarlo al actual cuando también          */
 /* la subrutina vaya regresando recurrentemente hasta despachar   */
 /* toda la cadena de llamadas para devolver el valor final        */
 /***/
  return (arr_ptr.pos >= arr_ptr.arr.length)? 0 : arr_ptr.arr[arr_ptr.pos] + arguments.callee(arr_ptr);
};



alert(arrr(miarreglo));    /* Resultado: 55 */

void(0);


Ocupa más líneas de código pero con el potencial de consumir menos memoria al ejecutarse.


Esto es a lo que me refiero con recurrencia de datos o resultados sin ocupar mucha memoria acumulativa, útil en sistemas con memoria limitada pero a la decisión del implementador. También se podría emular la "tail recursion" usando bucles en lugar de llamadas puramente recurrentes. Así ya no estaríamos limitados por el espacio de memoria de pila:

http://stackoverflow.com/questions/33923/what-is-tail-recursion


Y como decía, sabiendo qué técnicas usan otros lenguajes para optimizar la recurrencia, se pueden codificar y hacer uso de estas manualmente en cualquier otro lenguaje y usar parte de los beneficios (dependiendo del nivel del lenguaje, y entre más bajo sea es más factible obtener más beneficios con optimidad), no mediante características o sintaxis del lenguaje sino que simplemente haciendo uso del algoritmo que usan.



Follow members gave a thank to your post:
« Última Modificación: julio 19, 2011, 03:01:20 pm por ~ »
Mi sitio web:
---- IP para archivo hosts (todos mis subdominios):
190.150.9.244 archefire.org

Desconectado Non Servium

  • Trade Count: (0)
  • Sv Member
  • ***
  • Thank You
  • -Given: 6
  • -Receive: 39
  • Mensajes: 426
  • Ilix Punx :)
Re: recursividad
« Respuesta #6 : julio 20, 2011, 04:52:46 pm »
Puu!! me toparon el disco  :thumbsup:  :sur: :sur: buena... creo q ya hay suficiente info para wilton milber
♫ Condenados a perder la libertad! Por no acatar las leyes que les asignaron. ♪ ♫
Decididos, decididos a emprender! Un camino largo y duro por no ser esclavos ♫


Watch