Factorische methode - recursief of iteratief? (Java)

Ik liep door het project Euler en kwam een ​​combinatieprobleem tegen. Combinatie-logica betekent uitwerken van faculteiten. Dus besloot ik om een ​​faculteit-methode te maken. En toen raakte ik op een probleem - aangezien ik vrij gemakkelijk zowel iteratie als recursie kon gebruiken om dit te doen, voor welke moet ik gaan? Ik schreef snel 2 methoden - iteratief:

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;
        }

en recursief:

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

Als ik hier (uiteraard) praat over snelheid en functionaliteit, welke moet ik dan gebruiken? En, in het algemeen, is een van de technieken over het algemeen beter dan de andere (dus als ik deze keuze later tegenkom, waar moet ik dan voor gaan)?

 4
toegevoegd bewerkt
Bekeken: 4
de bron
ja ru es pt de
mogelijk duplicaat van Is recursie ooit sneller dan looping?
toegevoegd de auteur Kazekage Gaara, de bron
@luketorjussen - omdat ik met de lage aantallen die ik behandel en vanwege het feit dat ik de methode slechts één of twee keer noem, ik het verschil niet zou opmerken. Waar ik het over heb is als ik deze methode heel vaak gebruik, of over meer gecompliceerde methoden die beide technieken kunnen gebruiken.
toegevoegd de auteur Bluefire, de bron
@luketorjussen - eerlijk genoeg
toegevoegd de auteur Bluefire, de bron
De iteratieve versie lijkt overdreven complex. Het kan worden teruggebracht tot int res = 1; for (int i = 2; i <= num; ++ i) res * = i; return res;
toegevoegd de auteur Niklas B., de bron
De iteratief zal sneller zijn dan de recursieve in Java - maar dat maakt misschien niet uit (recursief hebben methodeaanroep-overhead die misschien niet is geoptimaliseerd) en Java is nog geen Regeling voor zover ik weet). Voor verdere excursies: chaosinmotion.com/blog/?p=622
toegevoegd de auteur esej, de bron
Waarom probeer je niet allebei en kijk je wat sneller is? Ook hoef je niet ver te gaan als het controleren of num == 0 , als num == 1 dan kun je 1 retourneren, waarom een ​​extra iteratie/functieaanroep doen
toegevoegd de auteur luketorjussen, de bron
@Bluefire, waarom probeer je het dan niet met grote cijfers en noem je het vaak?
toegevoegd de auteur luketorjussen, de bron

4 antwoord

Beide zijn hopeloos naïef. Geen enkele serieuze toepassing van faculteit zou een van beide gebruiken. Ik denk dat beide inefficiënt zijn voor grote n, en noch int noch long zullen voldoende zijn als het argument groot is.

Een betere manier zou zijn om een ​​goede gammafunctie implementatie en memo-opname te gebruiken.

Here's an implementation from Robert Sedgewick.

Voor grote waarden zijn logaritmen vereist.

13
toegevoegd
de bron
Ik ben het respectvol mee oneens.
toegevoegd de auteur duffymo, de bron
Ik denk dat het beter is na de bewerking :) Het intrekken van mijn eerdere opmerking
toegevoegd de auteur Niklas B., de bron

Wanneer u een optie krijgt om te kiezen tussen recursie en iteratie, ga dan altijd voor iteratie omdat

1.Recursie omvat het maken en vernietigen van stapelframes, wat hoge kosten met zich meebrengt.

2. Uw stack kan opblazen als u aanzienlijk grote waarden gebruikt.

Dus ga alleen voor recursie als je een aantal echt verleidelijke redenen hebt.

0
toegevoegd
de bron
Het maken en vernietigen van stapelframes heeft geen hoge kosten. Staartrecursie zoals deze kan door de taalprocessor worden weggeoptimaliseerd. Recursie is vaak een meer natuurlijke manier om een ​​berekening uit te drukken en de kosten kunnen onbeduidend zijn.
toegevoegd de auteur EJP, de bron

Er is geen "dit is beter, dat is erger" voor deze vraag. Omdat moderne computers zo sterk zijn, lijkt het in Java een persoonlijke voorkeur te zijn die je gebruikt. U doet veel meer controles en berekeningen in de iteratieve versie, maar u stapelt meer methoden op de stapel in de recursieve versie. Voors en tegens bij elk, dus je moet het van geval tot geval bekijken.

Persoonlijk houd ik me aan iteratieve algoritmen om de logica van recursie te vermijden.

0
toegevoegd
de bron
U doet niet meer controles of berekeningen in de iteratieve versie.
toegevoegd de auteur Niklas B., de bron
Oh, dus je hebt het over de complexiteit van de code. In dat geval ben ik het daarmee eens. Ik dacht dat je het had over runtime-complexiteit (omdat in beide versies hetzelfde aantal vermenigvuldigingen zal worden uitgevoerd).
toegevoegd de auteur Niklas B., de bron
@NiklasB. Als mijn telling klopt, controleert hij de start num == 0 , i <= num , i ++ , resultaat * = i in de iteratieve versie, terwijl hij in recursief num == 0 en num * faculteit (num - 1) heeft, half zoveel .
toegevoegd de auteur Odiefrom, de bron

Ik analyseerde dit probleem eigenlijk per tijdsfactor. Ik heb 2 eenvoudige implementaties gedaan:

iteratieve:

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;
}

En recursief:

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

Test allebei op één draad. Het blijkt dat iteratief iets sneller is alleen met kleine argumenten. Toen ik n groter dan 100 plaatste, was de recursieve oplossing sneller. Mijn conclussie? Je kunt nooit zeggen dat de iteratieve oplossing sneller is dan recursief op JVM. (Nog steeds alleen over tijd praten)

Als je intresse hebt, krijg ik de hele weg HIER

If You're intrested in deeper understanding difference between this 2 approaches, I found really nice description on knowledge-cess.com

0
toegevoegd
de bron