algorithm - recursivos - recursividad en programacion

¿Cómo escribirías un algoritmo no recursivo para calcular los factoriales?

Question

¿Cómo escribirías un algoritmo no recursivo para calcular n! ?

Answer 1

A menos que tenga enteros de longitud arbitraria como en Python, almacenaría los valores precalculados de factorial () en una matriz de aproximadamente 20 largos, y usaría el argumento n como índice. La tasa de crecimiento de n! es bastante alto, y computa 20! o 21! Obtendrá un desbordamiento de todos modos, incluso en máquinas de 64 bits.

Answer 2

Aquí está la función precalculada, excepto en realidad correcta. Como se dijo, 13! se desborda, por lo que no tiene sentido calcular un rango tan pequeño de valores. 64 bit es más grande, pero esperaría que el rango aún sea bastante razonable.

int factorial(int i) {
    static int factorials[] = {1, 1, 2, 6, 24, 120, 720, 
            5040, 40320, 362880, 3628800, 39916800, 479001600};
    if (i<0 || i>12) {
        fprintf(stderr, "Factorial input out of range/n");
        exit(EXIT_FAILURE); // You could also return an error code here
    }
    return factorials[i];
} 

Fuente: http://ctips.pbwiki.com/Factorial

Answer 3

Pseudo código

total = 1
For i = 1 To n
    total *= i
Next

Answer 4

Reescribe la solución recursiva como un bucle.

Answer 5

en pseudocódigo

ans = 1
for i = n down to 2
  ans = ans * i
next

Answer 6

fac = 1 ; 
for( i = 1 ; i <= n ; i++){
   fac = fac * i ;
}

Answer 7

int total = 1
loop while n > 1
    total = total * n
    n--
end while

Answer 8

long fact(int n) {
    long x = 1;
    for(int i = 1; i <= n; i++) {
        x *= i;
    }
    return x;
}

Answer 9

public double factorial(int n) {
    double result = 1;
    for(double i = 2; i<=n; ++i) {
        result *= i;
    }
    return result;
}

Answer 10

public int factorialNonRecurse(int n) {
    int product = 1;

    for (int i = 2; i <= n; i++) {
        product *= i;
    }

    return product;
}

Answer 11

En interés de la ciencia, realicé algunos perfiles sobre varias implementaciones de algoritmos para calcular factoriales. Creé implementaciones iterativas, de búsqueda y recursivas de cada una en C # y C ++. ¡Limité el valor de entrada máximo a 12 o menos, desde 13! es mayor que 2 ^ 32 (el valor máximo capaz de mantenerse en una int de 32 bits). Luego, ejecuté cada función 10 millones de veces, alternando entre los posibles valores de entrada (es decir, incrementando i de 0 a 10 millones, usando i modulo 13 como parámetro de entrada).

Aquí están los tiempos de ejecución relativos para diferentes implementaciones normalizadas a las figuras iterativas de C ++:

            C++    C#
---------------------
Iterative   1.0   1.6
Lookup      .28   1.1
Recursive   2.4   2.6

Y, para completar, aquí están los tiempos de ejecución relativos para implementaciones que usan enteros de 64 bits y que permiten valores de entrada de hasta 20:

            C++    C#
---------------------
Iterative   1.0   2.9
Lookup      .16   .53
Recursive   1.9   3.9

Answer 12

suponiendo que quisiera ser capaz de lidiar con algunos números realmente grandes, lo codificaría de la siguiente manera. Esta implementación sería para si deseabas una cantidad decente de velocidad para casos comunes (números bajos), pero quería poder manejar algunos cálculos súper fuertes. Consideraría que esta es la respuesta más completa en teoría. En la práctica, dudo que necesites calcular factoriales tan grandes para algo que no sea un problema de tarea.

#define int MAX_PRECALCFACTORIAL = 13;

public double factorial(int n) {
  ASSERT(n>0);
  int[MAX_PRECALCFACTORIAL] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
                362880, 3628800, 39916800, 479001600};
  if(n < MAX_PRECALCFACTORIAL)
    return (double)fact[n];

  //else we are at least n big
  double total = (float)fact[MAX_PRECALCFACTORIAL-1]
  for(int i = MAX_PRECALCFACTORIAL; i <= n; i++)
  {
    total *= (double)i;  //cost of incrimenting a double often equal or more than casting
  }
  return total;

}

Answer 13

Yo usaría la memorización. De esta forma, puede escribir el método como una llamada recursiva y obtener la mayoría de los beneficios de una implementación lineal.

Answer 14

int fact(int n){
    int r = 1;
    for(int i = 1; i <= n; i++) r *= i;
    return r;
}

Answer 15

¡Como un Int32 se desbordará en algo más grande que 12! de todos modos, solo hazlo:

public int factorial(int n) {
  int[] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
                362880, 3628800, 39916800, 479001600};
  return fact[n];
}

Answer 16

Me encanta la solución pitonica a esto:

def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))

Answer 17

En tiempo de ejecución esto no es recursivo. En tiempo de compilación es recursivo. El rendimiento en tiempo de ejecución debe ser O (1).

//Note: many compilers have an upper limit on the number of recursive templates allowed.

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}

Answer 18

long fact(int n)
{
    long fact=1;
    while(n>1)
      fact*=n--;
    return fact;
}

long fact(int n)
{
   for(long fact=1;n>1;n--)
      fact*=n;
   return fact;
}

Answer 19

Iterativo:

int answer = 1;
for (int i = 1; i <= n; i++){
    answer *= i;
}

O ... usando recursividad de cola en Haskell:

factorial x =
    tailFact x 1
    where tailFact 0 a = a
        tailFact n a = tailFact (n - 1) (n * a)

Lo que hace la recursión de cola en este caso es usar un acumulador para evitar acumular llamadas en la pila.

Referencia: Recursividad de cola en Haskell

Answer 20

Recursivamente usando JavaScript con el almacenamiento en caché.

var fc = []
function factorial( n ) {
   return fc[ n ] || ( ( n - 1 && n != 0 ) && 
          ( fc[ n ] = n * factorial( n - 1 ) ) ) || 1;
}

Answer 21

Factorial no recursivo en Java. Esta solución es con un iterador personalizado (para demostrar el uso del iterador :)).

/** 
 * Non recursive factorial. Iterator version,
 */
package factiterator;

import java.math.BigInteger;
import java.util.Iterator;

public class FactIterator
{   
    public static void main(String[] args)
    {
        Iterable<BigInteger> fact = new Iterable<BigInteger>()
        {
            @Override
            public Iterator<BigInteger> iterator()
            {
                return new Iterator<BigInteger>()
                {
                    BigInteger     i = BigInteger.ONE;
                    BigInteger total = BigInteger.ONE;

                    @Override
                    public boolean hasNext()
                    {
                        return true;
                    }

                    @Override
                    public BigInteger next()
                    {                        
                        total = total.multiply(i);
                        i = i.add(BigInteger.ONE);
                        return total;
                    }

                    @Override
                    public void remove()
                    {
                        throw new UnsupportedOperationException();
                    }
                };
            }
        };
        int i = 1;
        for (BigInteger f : fact)
        {
            System.out.format("%d! is %s%n", i++, f);
        }
    }
}