Fibonacci som rekursiv

Hej Jesper

Jeg har engang løst en lignende opgave, og du skal kalde din metode 2 gange rekursivt, bare med et andet term/nummer. Min løsning hurtigt kunne se således ud

 /**
  * Fibonacci takes the sum of the two previous numbers in the row. The term has to be a non negative number
  * @param term The term where we want the fibonacci number to be found.
  * @return The found fibonacci number.
  * @throws ArithmeticException is thrown if the term is negative.
  */
 public long fibonacci(int term)
        throws ArithmeticException
 {
     //our term has to be zero or positive.
     if (term >= 0) {
         //return the term if it's 0 or 1. This is our sentinel!
         if (term == 0 || term == 1)
         {
             return term;
         }
         else
         {
             //Return the result of 2 recursive method calls.
             return fibonacci(term - 1) + fibonacci(term - 2);
         }
     } else {
         //Is thrown if our term is negative.
         throw new ArithmeticException();
     }
 }

Som du kan se returnerer jeg resultatet af 2 rekursive kald, bare hvor den første har et nummer mindre end før, og den anden to numre mindre. på den måde opnår du effekten af at det foregående resultat adderes med det næste fibonacci tal i rækken.

håber at du kunne bruge dette til noget, og hvis du er i tvivl er du velkommen til at spørge.

 public static long fibonacci(int n) throw new ArithmeticException(); {
   if (n < 0)
     throw new ArithmeticException();
   if (n < 2)
     return n;
   else
     return fibonacci(n-1) + fibonacci(n-2);
 }

Det smarte ved rekursive funktioner er, at opgaver typisk bliver meget nemmere at løse. Ulempen er dog, at med mindre man bruger tail recursion, så ender metodekald med at blive utroligt langsomme, idet de forgræner sig så meget. Overvej fx her, at der vil være omkring 2^n kald til fibonacci-metoden blot for at beregne de n første fibonacci-tal.

Martin: Så benyt iteration, når performance er super vigtig, og benyt rekursion når performance ikke er så vigtig, men måske mere læsbarheden. Det er hvertfald hvad jeg har fået fortalt.

Jeg vil ikke engang sige, at han skal benytte det, når det er super vigtigt, men bare når performance har den mindste indflydelse. Udførselshastigheden bliver eksponentielt større, dvs. en udregning, der måske ville tage 2 sekunder kan ende med at tage flere minutter. Det er ikke bare et lille performanceudsving, rekursion kan skabe.

Det helt store problem med rekursiv udregning af fibonacci tal er ikke at der skal gemmes resultater, men snarere at mange beregninger skal udregnes mange gange. Jeg har lavet et træ til at vise, hvad der skal til, for at beregne det 10. fibonacci tal rekursivt: http://www.the-playground.dk/uploads/images/software/fib.png

fib(10) kalder videre til fib(9) og fib(8). fib(9) kalder så også videre til fib(8) og fib(7), og så videre.
Som det kan ses, så bliver de samme beregninger og subtræer, beregnet mange gange, og det bliver værre for høje fibonacci tal.

Jeg brugte følgende kode til at generere tegningen:

 #include <stdio.h>
 #include <stdlib.h>
 
 int _fib(int num, int caller) {
     static int invocation_count = 0;
     int me = invocation_count++;
     printf("    fib_%d [label=\"fib(%d)\"];\n", me, num);
     if (caller >= 0) {
         printf("    fib_%d -> fib_%d;\n", caller, me);
     }
     return num <= 2 ? 1 : _fib(num - 1, me) + _fib(num - 2, me);
 }
 
 int fib(int num) {
     return _fib(num, -1);
 }
 
 int main(int argc, const char *argv[]) {
     int num = argc > 1 ? atoi(argv[1]) : 10;
     printf("digraph G {\n");
     fib(num);
     printf("}\n");
     return 0;
 }

Resultatet fodrede jeg til Graphiviz Dot værktøjet, som kan hentes herfra: http://www.graphviz.org/

En anden ting som er en væsentlig forskel på rekursion og den iterative løsning, udover mulige forskelle i performance, er at for hvert rekursiv kald så vil stakken (indeholder lokal variabler for alle funktioner/metoder som er under udførsel) vokse. I ekstreme tilfælde kan det betyde at stakken kan blive for stor og dette vil i de fleste programmeringssprog skabe noget lignende en StackOverflowException. Dette er typisk de samme tilfælde dog hvor den rekursive metode i forvejen ville have været alt for langsom langt før dette problem ville have opstået dog.

Det skal måske nævnes i samme ombæring at på trods af i f.eks. fibonacci tilfældet så har rekursion en "straf" - stakken vokser som sagt for hvert metode kald og dette koster en smule i performance. Typisk vil dette ikke være nok til at man bør tænke for meget på det, men er man i ekstreme miljøer er det værd at tænke over. Det skal selvfølgelig noteres her at der antages at der ikke er tale om tail recursion eller at det sprog man bruger ikke har en compiler som optimerer for dette (kort sagt - der findes en form for rekursion som kan, når man kompillerer sin kode, omskrives til en iterativ version - i visse sprog sker dette, f.eks. Haskell, Lisp og diverse andre funktionelle sprog)

Rekursion og løkker er to forskellige måder at arbejde på, så nej, det vil ikke (nødvendigvis) være relevant at begge tæller op.

Var måske en dårlig måde at forklare hvad jeg mente. Det jeg ville frem til var, at hvis i ønsker at sammenligne de to teknikker burde i sammenligne den bedste løsning i hver teknik.

Ikke at jeg forventer at rekursion derfor bliver bedre end løkken i dette tilfælde, men den bliver væsentlig mindre dårligere.

Man kan sige at rekursive metoder på mange måder er lettere at læse og hurtigere at implementere end iterative metoder (metoder der benytter løkker). Der er dog en stor ulempe med rekursion, nemlig den at hver gang vi udfører et rekursivt kald er vi nødt til at gemme resultatet, samt andre lokale variabler på stakken, hvilket betyder at hvis vi skulle finde fibonacci med et stort tal, så vil det tage lang tid for computeren at udføre i forhold til en iterativ metode. Du behøver nemlig ikke gemme mange resultater osv. i nye variabler, hvis metoden er iterativ.

Så benyt iteration, når performance er super vigtig, og benyt rekursion når performance ikke er så vigtig, men måske mere læsbarheden. Det er hvertfald hvad jeg har fået fortalt

Så benyt iteration, når performance er super vigtig, og benyt rekursion når performance ikke er så vigtig, men måske mere læsbarheden. Det er hvertfald hvad jeg har fået fortalt

Det er også rigtigt efter mine erfaringer.
Nu udvikler jeg godt nok i .NET men da jeg har haft lavet et større distribueret "bruteforce grid" med flere computere, hvor performance VAR super vigtig, der kunne jeg se et væsentligt performance hit ved rekursion i forhold til iteration. Og det var præcist den samme metode jeg havde implementeret.

Nu ved jeg godt at .NET heller ikke lige frem er berømt for sin rekursion, men just my five cents

Rekursion er godt til mange ting, men lige nøjagtig fibonacci er det er virkelig skidt løsning, da den beregner de samme dele mange gange.
Når du er færdig, så prøv at beregne det 30. fibonacci tal med henholdsvis rekursion og en løkke. Stor forskel.

Performance ved en løkke kan være ligeså god som ved rekursion, det kommer helt an på opgaven.
Skal du f.eks. beregne hvor mange data, der ligger i et bibliotek og underbiblioteker, så kan man bruge en løkke, men det vil være meget mere læsbart at bruge rekursion, og performancemæssigt vil det være det samme (eller forskellen vil være ubetydelig).
Pattern matching og parsing er noget nær umulig at gøre korrekt uden rekursion.

Fibonacci er bare det klokkeklare eksempel på at rekursion ikke altid er det korrekte at bruge.

Jeg vil gerne bede om en præcis forklaring på hvorfor min metode ikke er rekursiv..