Factorielle de la méthode récursive ou itérative? (Java)

J'ai été faire mon chemin à travers le projet Euler, et je suis tombé sur une combinaison de problème. Combinaison logique de moyens de travail hors factorielles. Donc, j'ai décidé de créer une méthode factorielle. Et puis, je suis tombé sur un problème depuis que j'ai pu assez facilement utiliser à la fois l'itération et la récursivité pour ce faire, laquelle dois-je aller? J'ai rapidement écrit 2 méthodes itératives:

public static long factorial(int num) {
        long result = 1;
        if(num == 0) {
            return 1;
        }
        else {
            for(int i = 2; i <= num; i++) {
                result *= i;
            }
            return result;
        }

et récursive:

public static long factorial(int num) {
        if(num == 0) {
            return 1;
        }
        else {
            return num * factorial(num - 1);
        }
    }

Si je suis (évidemment) en parlant de la vitesse et de fonctionnalité, qui dois-je utiliser? Et, en général, est l'une des techniques généralement mieux que les autres (donc, si je viens à travers ce choix plus tard, que dois-je aller pour)?

double possible de la récursivité Est toujours plus rapide que la boucle?
parce qu'avec le faible nombre d'-je traiter et en raison du fait que je ne l'appel à la méthode une fois ou deux fois, je ne remarque pas la différence. Ce que je veux dire c'est que si j'utilise cette méthode des charges et des charges de temps, ou plus compliqué méthodes que peuvent utiliser les deux techniques.
Pourquoi n'essayez-vous pas à la fois et de voir laquelle est la plus rapide? Aussi, vous n'avez pas besoin d'aller loin que de vérifier si num == 0, si num == 1 ensuite, vous pouvez revenir 1, pourquoi faire un extra itération/appel de la fonction
juste assez
La version itérative semble trop complexe. Il pourrait être réduit à int res = 1; for (int i = 2; i <= num; ++i) res *= i; return res;

OriginalL'auteur Bluefire | 2012-06-23

  1. 13

    Les deux sont désespérément naïf. Pas sérieux de demande de factorielle serait d'utiliser l'un des deux. Je pense que les deux sont inefficaces pour n grand, et ni int ni long suffira quand l'argument est grande.

    Une meilleure approche serait d'utiliser un bon la fonction gamma mise en œuvre et de memoization.

    Voici de mise en œuvre de Robert Sedgewick.

    Grandes valeurs nécessiteront des logarithmes.

    Je vais respectueusement en désaccord.
    Je pense que c'est mieux après le montage 🙂 la Rétraction de mon commentaire précédent

    OriginalL'auteur duffymo

  2. 0

    Il n'y a pas de "c'est mieux, c'est pire" pour cette question. Parce que les ordinateurs modernes sont si forts, en Java, il a tendance à être une préférence personnelle que vous utilisez. Vous faites beaucoup plus de contrôles et calculs dans la version itérative, cependant, vous empilez plusieurs méthodes dans la pile dans une version récursive. Les avantages et les inconvénients de chacun, de sorte que vous avez à prendre au cas par cas.

    Personnellement, je colle avec les algorithmes itératifs pour éviter la logique de la récursivité.

    Vous n'êtes pas en faire plus de vérifications ou des calculs dans la version itérative.
    Si mon compte est bon, il est en train de faire un chèque pour le départ num == 0, i <= num, i++, result *= i dans la version itérative, tandis que dans le récursive, il a num == 0 et num * factorial(num - 1), de la moitié du nombre.
    Oh, vous parlez de la complexité du code. Dans ce cas je suis d'accord. Je pensais que vous parliez d'exécution de la complexité (parce qu'après tout, le même nombre de multiplications seront effectués dans les deux versions).

    OriginalL'auteur Odiefrom

  3. 0

    Chaque fois que vous obtenez une option pour choisir entre la récursivité et itération, toujours aller pour l'itération car

    1.La récursivité implique la création et la destruction de la pile des cadres, qui a des coûts élevés.

    2.Votre pile peut exploser si vous utilisez de manière significative les grandes valeurs.

    Alors, allez pour la récursivité uniquement si vous en avez vraiment tentant raisons.

    La création et la destruction de la pile des cadres ne pas avoir un coût élevé. La queue de la récursivité comme cela peut être optimisé par le langage du processeur. La récursivité est souvent un moyen plus naturel pour exprimer un calcul et que les coûts peuvent être négligeable.

    OriginalL'auteur Ahmad

  4. 0

    J'étais en fait l'analyse de ce problème par le facteur temps.
    J'ai fait 2 implémentations simples:

    Itératif:

    private static BigInteger bigIterativeFactorial(int x) {
    BigInteger result = BigInteger.ONE;
    for (int i = x; i > 0; i--)
        result = result.multiply(BigInteger.valueOf(i));
    return result;
}

    Et Récursive:

    public static BigInteger bigRecursiveFactorial(int x) {
    if (x == 0)
        return BigInteger.ONE;
    else
        return bigRecursiveFactorial(x - 1).multiply(BigInteger.valueOf(x));
}

    Tests à la fois en cours d'exécution sur un seul thread.
    Il s'avère que Itératif est légèrement plus rapide qu'avec les petits arguments. Quand j'ai mis n plus grand que 100 solution récursive a été plus rapide.
    Mon conclussion? Vous ne pouvez jamais dire que la solution itérative est plus rapide que récursive sur la JVM. (Toujours en ne parlant que de temps)

    Si Vous êtes intéressé, de toute façon, je reçois ce conclussion est ICI

    Si Vous êtes intéressé par l'une compréhension plus profonde différence entre ces 2 approches, je l'ai trouvé vraiment belle description sur knowledge-cess.com

    OriginalL'auteur Filip Kubala