Fibonacci som rekursiv

Din metode kalder ikke sig selv indtil "base case" rammes

Hvis i vil sammenligne rekursion og løkker er det vel rimelig relevant, at i faktisk foretager det samme.

Løkken starter ved fib 3 til fib n. Mens rekursionen starter ved fib n til fib 1.

Så hvis i vil sammenligne burde i starte rekursionen ved fib 3 og rekursere op ad. (Burde være muligt.)

noget i retning af dette (javascript udgaven):

function _fib(a, b, n){
  if(n<2) return a;
  return _fib(a + b, a, n-1);
}

function fib(n){
  if(n<1) return 0;
  return _fib(1, 0, n);
}
alert(fib(1));

Har du iøvrigt prøvet at teste din løkke med:
fibonacci(1)
fibonacci(2)
Tror ikke det vil give dig 1, men derimod 0.

Dejligt med denne tråd.... Jeg lærer faktisk noget her

@Robert - Rekursion stammer mere eller mindre fra den matematiske måde at tænke på tingene på. Hvis du synes det er rart at arbejde med bør du prøve at udforske nogle af de funktionelle sprog der findes. Hvis man godt kan lide den matematiske tankegang der findes, og således godt kan lide at vende problemerne lidt om (som man fint kan argumentere for at den simple rekursive løsning på fibbonacci er ifht. den iterative løsning) - så findes der altså nogle sprog som er herlige at skrive i. Jeg er selv i færd med at lave en compiler i Ocaml som en del af min uddannelse - og jeg synes godt nok at jeg bliver mere og mere glad for sproget jo mere jeg skriver i det. Desværre kan man godt mærke at compileren ikke er helt så optimeret ifht. fejl beskeder - men selve sproget må jeg indrømme jeg er blevet glad for.

@Kaare Helt enig. Funktionelle sprog er da ganske sjove, og har også leget lidt med Clojure men stoppede pga. tidsmangel.
Skal dog tage det op igen på et tidspunkt.

Hej Jens, Din metode er jo ikke rekursiv?? eller??

Martin: Tak, det var lige det jeg havde brug for. Forresten hvad er egentlig forskellen ved metoden med løkker og metoden med rekursion?

Martin > Okay, jeg er med. Min kodestil er bare generelt at jeg undgår at kalde den samme metode inde i sig selv, ved ikke hvorfor jeg har fået denne opfattelse..

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.

Din rekursive metode er bestemt mere optimal end de tidligere, men den er også tættere op ad løkken, som vil være mere logisk at bruge...og en smule hurtigere og vil bruge hukommelsen bedre.

Man kan også traversere en træstruktur uden rekursion, men her er rekursion typisk bare en meget elegant metode, mens en løkke ville blive ret kompleks. Traversering af et array eller kædet liste, vil derimod blive bedst med en løkke frem for rekursion.

hehe...så er vi enige jens :-)


Nu har der været en del kritik af rekursion i denne tråd, så jeg vil lige give min dybeste respekt til ham som fandt på det. Rekursion er fandeme en elegant teknik, men ligesom med alle andre teknikker skal man vide, hvordan den virker, for at kunne bruge den korrekt, og for at vide, hvor den bør og ikke bør bruges.

Jeg har haft en opgave der ligner meget, og såvidt jeg ved, så skal man bruge det forgående resultat, og ligge sammen med det tal du er i gang med at behandle, så jeg synes din kode ser fin ud, dog mangler der ligesom en start, som beskriver hvad dine start-værdier er.

 public class Fibonacci {
     // Fra hvor mange tal skal regnes? (n)
     public static final int COUNT = 25; 
 
     // Værdien for det første fibonacci tal (n=1)
     public static int f1 = 1;
     // Værdien for det andet fibonacci tal (n=2)
     public static int f2 = 1; 
     // Værdien for det tal som kommer til at blive opdateret løbende
     public static int f = 0; 
 
     public static void main(String[] args){
         for(int i=1;i<=2;i++){
             System.out.print(1 + " ");
             f1=1;
             f2=1;
         }
         for(int i=3;i<=COUNT;i++) // find tal op til n
         {
             f = f1 + f2;
             System.out.print(f + " ");
             f2=f1;
             f1=f;
         }
     }
 }