Optimización de Algoritmo Recursivo

Publicado en 'Programación' por n00b, 18 Nov 2016.





  1. n00b

    n00b Miembro frecuente

    Registro:
    12 Dic 2015
    Mensajes:
    156
    Likes:
    53
    Temas:
    5




    Buenas estimados, espero me puedan ayudar con lo sigte:
    Técnicas para la optimización de un algoritmo recursivo, o si pueden recomendarme algun/os libros, links, etc.
    Una técnica es usar un loop (for, while,..).

    Un ejemplo de un algoritmo recursivo podría ser el típico calculo del factorial.
    PHP:
    int factorial(int number) {
        
    int temp;

        if(
    number == 0) return 1;

        
    temp number factorial(number 1);
        return 
    temp;
    }


    Gracias.

    PD. Disculpen lo escueto del tema, debe ser porque me estoy durmiendo.
     


  2. anthony23

    anthony23 Miembro maestro

    Registro:
    5 Dic 2015
    Mensajes:
    409
    Likes:
    15
    Temas:
    106
    el for
    mi profe me dijo que solo en algunos casos es mejor irse por la recursividad
     
    A n00b le gustó este mensaje.
  3. eduar2083

    eduar2083 Miembro frecuente

    Registro:
    26 Jul 2011
    Mensajes:
    246
    Likes:
    54
    Temas:
    22
    Hola,

    Tal como está, funciona correctamente, pero puedes ahorrarte una llamada recursiva cuando number=1 ya que también es igual 1

    Código:
    int factorial(int number) {
        if(number == 0 || number == 1) return 1;
     
        return number * factorial(number - 1);
    }
    Debes considerar también que el factorial tiende a crecer exponencialmente a medida que number es mayor y la variable de retorno int se debordará tan pronto como llegue a su valor máximo, por ello, se sugiere utilizar el tipo double, debes considerar que el tipo que recibe el valor de retorno debe ser también double.
    Código:
    double factorial(int number) {
        if(number == 0 || number == 1) return 1;
     
        return number * factorial(number - 1);
    }
    Saludos.
     
    A anthony23 y n00b les gustó este mensaje.
  4. gnox

    gnox Miembro de bronce

    Registro:
    3 Ene 2013
    Mensajes:
    2,348
    Likes:
    945
    Temas:
    82
    La mejor optimización es evitarlo, en los ejemplos que ponen no consideran que pueden llegar a un stack overflow (almacenamiento de variables y/o llamadas de funciones en memoria) o como ya dijeron a valor en un rango mayor al tipo de devolución. O controlas la profundidad de la recursion o cambias mejor a funciones iterativas .
     
    A n00b le gustó este mensaje.
  5. kgb1968

    kgb1968 Miembro de oro

    Registro:
    16 Nov 2008
    Mensajes:
    6,402
    Likes:
    1,888
    Temas:
    141
    Este tema me trae gratos recuerdos, te recomiendo este libro de N. Wirth, es sobre estructuras de datos.
     
    A n00b le gustó este mensaje.
  6. eduar2083

    eduar2083 Miembro frecuente

    Registro:
    26 Jul 2011
    Mensajes:
    246
    Likes:
    54
    Temas:
    22
    Para este ejemplo, lo más probable que siempre ocurra primero es el desbordamiento de variable de retorno que el desbordamiento de pila.
     
    A anthony23 le gustó este mensaje.
  7. n00b

    n00b Miembro frecuente

    Registro:
    12 Dic 2015
    Mensajes:
    156
    Likes:
    53
    Temas:
    5
    Gracias a todos por sus respuestas.
    He estado viendo y al parecer, tal vez me equivoque, para esta función específicamente y en términos de Big O no hay optimización, ni con el ejemplo propuesto por el forista @eduar2083 , ni pasando, como dije al principio, a un loop:

    La versión de la función usando recursión es de una complejidad de O(n) y la complejidad para la versión usando loop es de O(n) también.

    Lo que sí optimizaría el cálculo sería hacer una implementación del algoritmo Schönhage–Strassen que permite hacer multiplicaciones más eficientes, pero esto solo aplicaría para este caso específico donde se necesita multiplicar.

    No soy un experto, me picó la curiosidad a raíz de un reto en el trabajo sobre esto.
     
    A anthony23 le gustó este mensaje.
  8. n00b

    n00b Miembro frecuente

    Registro:
    12 Dic 2015
    Mensajes:
    156
    Likes:
    53
    Temas:
    5
    Ya me dijeron la respuesta, la comparto:
    Memoization
     
    A anthony23 le gustó este mensaje.
  9. Automorphism

    Automorphism Miembro frecuente

    Registro:
    26 Ago 2012
    Mensajes:
    93
    Likes:
    27
    Temas:
    1
    Una forma particularmente importante de optimizar algoritmos recursivos es hacer que la llamada recursiva sea la última cosa que hace tu función. Esto es conocido en inglés como “tail recursion”:

    Código:
    int factorial_helper(int accumulator, int counter)
    {
        if (counter < 2)
            return accumulator;
        else
            return factorial_helper(accumulator * counter, counter - 1);
    }
    
    int factorial(int argument)
    {
        return factorial_helper(1, argument);
    }
    Observa que, desde un punto de vista lógico, esto es equivalente a la siguiente implementación iterativa:

    Código:
    int factorial(int argument)
    {
        int accumulator = 1;
        while (argument >= 2) {
            accumulator = accumulator * argument;
            argument = argument - 1;
        }
        return accumulator;
    }
     
    A n00b le gustó este mensaje.