# Fibonacci Folge



## sk72 (29. Aug 2011)

Hallo, 
Ich soll eine rekursive Darstellung der Fibonacci-Folge programmieren, allerdings komme ich einfach nicht voran.
Ich habe mit natürlich bereits einige Beispiele im Internet angeschaut, allerdings verstehe ich dabei oftmals den Kern des Codes nicht. 
Vielleicht kann mir jemand von euch helfen, einen einfachen Code mit Erklärung zu schreiben. 

Danke!


----------



## Volvagia (29. Aug 2011)

Neee, so läuft das hier nicht. Du kannst aber posten was du bereits hast, dann können wir dir dort weiterhelfen, wo du die Blockade hast.


----------



## Landei (29. Aug 2011)

Die naive rekursive Definition ist in diesem Fall einfach die direkte Umsetzung der mathematischen Definition: Für die ersten beiden Folgeglieder sind feste Werte vorgegeben, für alle weiteren Werte muss man zur Berechnung auf das letzte und vorletzte Folgeglied zurückgreifen:


```
public static long fib(int n) {
   if(n == 0) {
     return 0;
   } else if (n == 1) {
     return 1;
   } else {
      return fib(n-1) + fib(n-2); //der rekursive Aufruf
   }
}
```

Dich verwirren wahrscheinlich ausgefeiltere Implementierungen, denn die oben genannte ist furchtbar ineffektiv, weil für höhere Folgeglieder enorm viele frühere Glieder mehrfach berechnet werden müssen.


----------



## sk72 (29. Aug 2011)

Danke Landei

Was ich allerdings nicht verstehe, ist insbesondere Zeile 1 & Zeile 7.
Die if-Sätze _bedeuten_ ja lediglich, dass f(0) = 0 und f(1) = 1 ?!


----------



## Fab1 (29. Aug 2011)

Hi,

also Zeile 1 ist einfach nur eine Methode die einen Parameter erwartet. (oder was willst du da genau wissen)

bei Zeile 7 weis ich nicht wie ich es besser erklären kann 


Gruß


----------



## Andi_CH (29. Aug 2011)

sk72 hat gesagt.:


> Danke Landei
> 
> Was ich allerdings nicht verstehe, ist insbesondere Zeile 1 & Zeile 7.
> Die if-Sätze _bedeuten_ ja lediglich, dass f(0) = 0 und f(1) = 1 ?!



Schreiben wir es doch einmal in Pascal-ähnlichem code hin


```
public static long fib(int n) {
   if (n == 0)  then {
     return 0;
   } else if then (n == 1) then {
     return 1;
   } else {
      return fib(n-1) + fib(n-2); //der rekursive Aufruf
   }
}
```

oder Deutsch:

```
public static long fib(int n) {
   wenn (n == 0)  dann {
     return 0;
   } wenn (n == 1) dann {
     return 1;
   } wenn etwas anderes {
      return fib(n-1) + fib(n-2); //der rekursive Aufruf
   }
}
```

und wenn du lieber TO das nun nicht auf die dir sicher vorliegende mathematische Definition der Fiboncci Reihe legen kannst, bist du im falschen Forum.
--
"If-Sätze" ???:L   Na ja, wenigstens nicht if-Schleife


----------



## 0x7F800000 (29. Aug 2011)

Ich hab' zwar (ähnlich wie Landei) auch schon längst den totalen Scala-Schaden, und benutze selten stinknormale for-int-i-Schleifen , aber vielleicht erscheint dir die Version ohne Rekursionen und If's einfacher:

```
import static java.lang.System.*;

public class Fibonacci {
	public static long fib(int n){
		long a = 0, b = 1;
		for (int i = 0; i < n; i++) b = a + (a = b);
		return a;
	}
	
	public static void main(String... _){
		for (int i = 0; i <= 50; i++) out.println(i + ":\t" + fib(i));
	}
}
```
Hab's extra kurz gehalten, damit du das nicht einfach als Hausaufgabe abgeben kannst, du musst ja auch irgendeinen Spaß am Knobeln haben^^ 

[kriegt's einer mit weniger token hin (long nach int und variablennamen ändern zählt nicht)? ]


----------



## Fab1 (29. Aug 2011)

sk72 hat gesagt.:


> Hallo,
> Ich soll eine rekursive Darstellung der Fibonacci-Folge programmieren
> 
> Danke!



Ich denke genau eine solche rekursive Darstellung wird der TO brauchen, obwohl ich selbst die Variante mit der for Schleife bevorzuge. (damit kann ich besser umgehen)

sk72 ich denke es wäre gut, wenn du dein Problem noch etwas spezifischer beschreiben könntest, damit wir uns einen besseren Überblick von deinem Problem machen können.


----------



## 0x7F800000 (29. Aug 2011)

GEEK hat gesagt.:


> Ich denke genau eine solche rekursive Darstellung wird der TO brauchen, obwohl ich selbst die Variante mit der for Schleife bevorzuge. (damit kann ich besser umgehen)



Ah, ok, danke, hab' die Frage nicht genau gelesen 

Ok, wenn schon, dann:

```
public static long fib(int n){ return n <= 1 ? n : fib( n - 1 ) + fib ( n - 2 ); }
```

Hat eindeutig weniger Token, auch wenn die Laufzeit furchtbar ist


----------



## musiKk (29. Aug 2011)

Und jeder weiß ja, dass das höchste Ziel von Hausaufgaben und Softwareentwicklung die Minimierung der Tokenzahl ist!


----------



## sk72 (29. Aug 2011)

Danke für die schnellen Antworten! 

Ich denke mittlerweile habe ich das Prinzip einigermaßen verstanden - zumindest glaube ich es !


```
return fib(n-1) + fib(n-2); //der rekursive Aufruf
```

In dieser Zeile werden sämtliche Fibonacci Folgen bis zum gesuchten n ausgerechnet, ist das so richtig ?

Und um zu wissen, dass Fib(0) = 0 und Fib(1) = 1 ist, benötigt man diese Zeilen:


```
if(n == 0) {
     return 0;
   } else if (n == 1) {
     return 1;
```
?
Dies ist notwendig, um Fib(2) zu berechnen ? Es werden dann folgenden zwei _Bedingungen_ mit einander addiert:

```
if(n == 0) {
     return 0;
```

und


```
} else if (n == 1) {
     return 1;
```

Stimmt das soweit ?


----------



## Andi_CH (29. Aug 2011)

Weisst du was ein Debuggger ist?
Weisst du wie system.out.println funktioniert?

Schau doch einfach selbst was wann wie und in welcher Reihenfolge mit welchen Werten ausgeführt wird ....

In anlehnung an einen songtext von Linda Ronstadt

It's so easy to ask around ...


----------



## Landei (29. Aug 2011)

Ja, stimmt ungefähr. Allerdings wird vieles mehrfach berechnet. Hier die hierarchischen Aufrufe von fib(5):

```
fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1) 
    fib(2)
      fib(1)
      fib(0)
  fib(3)
    fib(2)
      fib(1)
      fib(0)
    fib(1)
```

Wie du siehst, benötigt fib(5) die Werte von fib(4) und fib(3), aber fib(4) selbst braucht auch wieder fib(3) u.s.w. Diese Mehrfachberechnungen versucht man deshalb zu vermeiden (mit Arrays, Maps, paralleler Berechnung von 2 Werten, Matrixmultiplikation, andere Formeln u.s.w.)


----------



## 0x7F800000 (29. Aug 2011)

musiKk hat gesagt.:


> Und jeder weiß ja, dass das höchste Ziel von Hausaufgaben und Softwareentwicklung die Minimierung der Tokenzahl ist!


Jenau! 
Nein, mal im Ernst: ich fand einfach nur die separate Fallunterscheidung für n = 0 und n = 1 unnötig, geht ja auch mit einem <= , und es rennt nicht in unendlichschleife davon, wenn man mal was negatives eingibt 



sk72 hat gesagt.:


> Stimmt das soweit ?


"Bedingungen addiert" klingt komisch. Bevor du was ausimplementierst, ist es sehr hilfreich, wenn du weißt, was du da tust. Landei hat lediglich 1:1 die Definition

```
F(n) := { 
  0                     falls n = 0
  1                     falls n = 1
  F(n-1) + F(n-2)  sonst
```
in Java hingeschrieben. Wenn Du nicht mal die Definition verstehst, dann ist es zu früh, über java-code zu reden: nimm Bleistift, werte die Formel per hand für n = 1,2,3 aus.


----------



## sk72 (29. Aug 2011)

Die nötige mathematische Grundkenntnisse besitze ich schon, nur weiß ich leider nicht genau wie ich es jetzt in Java umsetzen muss.

Ich stehe noch ganz am Anfang meines Studiums und dementsprechend besitze ich auch kaum Kenntnisse in Java. 

Ich habe folgenden Code geschriebe, aber leider funktioniert das so nicht. 


```
public class FibonacciFolge {
	public static void main (String [] args) {
		long fib(int n);
		fib(0) = 0;
		fib(1) = 1;

		for(int i = 0; i <= 10; i++) {
			fib(n) = fib(n-1) + fib(n-2);
			System.out.println(fib(n));
		}		
	}
}
```

Wo stecken da die Fehler ?


----------



## Michael... (29. Aug 2011)

sk72 hat gesagt.:


> Wo stecken da die Fehler ?


Vor dem PC bzw. an den mangelnden Java bzw. Programmiergrundlagen ;-)
Fehler stecken quasi in fast jeder Zeile. Das ganz enthält "grammatikalische" Fehler und lässt sich so natürlich nicht kompilieren.
Sind Methoden ein Begriff und Deklaration primitiver Variablen ein Begriff?
Ich habe den Eindruck, dass auch die Rekursion grundsätzlich nicht verstanden wird. ? (eine Methode ruft sich selbst auf)
Ich würde mal mit etwas einfachem anfangen. z.B. gib alle Zahlen von 0 bis n rekursiv aus.

Versuchst Du jetzt das ganze doch iterativ (for Schleife), statt rekursiv zu lösen?


----------



## sk72 (29. Aug 2011)

Beides nur sehr bedingt und auf einfachstem Niveau.
Nein, das Problem soll rekursiv gelöst werden.
Doch, ich verstehe die Rekursion grundsätzlich schon - meine ich zumindest: F(n) ist die Summe beider Vorgänger ?!

Und nein, ich weiß auch nicht wie ich eine Rekursion aller Zahlen von 0 bis n in Java programmieren könnte. Mathematisch wäre das ja f(n) = f(n-1)+1 ?
Ich würde halt einfach eine for-Schleife durchlaufen lassen ? Aber das ist ja nicht rekursiv oder ?


----------



## Fu3L (29. Aug 2011)

sk72 hat gesagt.:


> Ich würde halt einfach eine for-Schleife durchlaufen lassen ? Aber das ist ja nicht rekursiv oder ?



Genau, das wäre iterativ. 



> Und nein, ich weiß auch nicht wie ich eine Rekursion aller Zahlen von 0 bis n in Java programmieren könnte. Mathematisch wäre das ja f(n) = f(n-1)+1 ?



Ja, das ist richtig 
Für die Rekursion: Du rufst die Funktion erst mit n (sagen wir 10) auf. In der Methode prüfst du dann, ob n = 0 ist, wenn ja, gibst du 0 aus und returnst. Wenn n != 0, dann rufst du deine funktion mit n-1 nochmals auf und gibst danach n aus. So wird immer und immer wieder n um 1 verringert, die Funktion geht immer "tiefer", bis es 0 wird, dann wird die Zahl ausgegeben und die Methode "steigt" wieder "auf" und gibt eine Zahl nach der anderen aus.


----------



## Sich (29. Aug 2011)

Also, im allgemeinen bezeichnet Rekursion eine Technik um eine Funktion durch sich selbst zu definieren. Dazu könntest du auch mal Wikipedia bemühen: Rekursion.


> Mathematisch wäre das ja f(n) = f(n-1)+1


 Das stimmt nicht, das würde ja bedeuten, dass f(5) = f(4)+1 = 4, aber richtig ist: f(5) = f(4)+f(3) vgl.: Fibonacci-Folge.
Also brauchst du um f(n) berechnen zu können f(n-1) und f(n-2)!
Der Algorithmus sieht, wie auch schon von 0x7F800000 geschrieben so aus:

```
F(n) := { 
  0                    falls n = 0
  1                    falls n = 1
  F(n-1) + F(n-2)      sonst
};
```
Das ist soweit der mathematische Hintergrund.
Um das nun in ein Stück Java-Code zu bringen, sollten jedoch die elementarsten Programmierkenntnisse vorhanden sein.
[offtopic] Obwohl ich mich immer wieder wundern muss, wieso man immer mit einer OO-Sprache das Programmieren lernen will/soll, da ist meiner Meinung nach eine Sprache wie Pascal um längen geeigneter.

Gruß
Sich


----------



## Landei (29. Aug 2011)

Mal nach Java übersetzt:


```
public class FibonacciFolge {
    public static void main (String [] args) {
        long[] fib = new long[10];
        fib[0] = 0;
        fib[1] = 1;
 
        for(int i = 2; i < fib.length; i++) {
            fib[n] = fib[n-1] + fib[n-2];
            System.out.println(fib[n]);
        }       
    }
}
```

Das ist so ziemlich das, was deinem Code am nächsten kommt, allerdings ist das eine iterative (und keine rekursive) Lösung. Normalerweise würde man das natürlich noch in eine extra Methode auslagern u.s.w.

Ich denke, du solltest dich jetzt nicht an diesem Problem festbeißen, sondern erst einmal die Grundlagen lernen: Variablenzuweisungen, Methoden, Arrays u.s.w.


----------



## sk72 (29. Aug 2011)

Sich hat gesagt.:


> Also, im allgemeinen bezeichnet Rekursion eine Technik um eine Funktion durch sich selbst zu definieren. Dazu könntest du auch mal Wikipedia bemühen: Rekursion.
> Das stimmt nicht, das würde ja bedeuten, dass f(5) = f(4)+1 = 4, aber richtig ist: f(5) = f(4)+f(3)
> 
> Gruß
> Sich




Es ging gerade um die Rekursion der natürlichen Zahlen {0,1,2,3,4,5 ... } und da sollte doch schon gelten: f(n) = f(n-1) + 1 ; f(0) = 0
 ?

Dazu habe ich mal folgenden Code geschrieben:


```
public class Rekursion{
    public static void main(String[] args){
    	int a=0;
    	while(a<=10) {
    		System.out.println(a);
    		a = a+1; // bzw a++;
    	}
        
    } 
}
```


----------



## Landei (29. Aug 2011)

Schleife -> iterativ
Methode ruft sich selbst auf -> rekursiv

Was ist dann dein Code?


----------



## Michael... (29. Aug 2011)

In folgendem Code gibt die Methode _printNext_ die Zahlen von 0 bis n rekursiv aus.
Ich habe mal versucht den Code möglichst einfach und verständlich zu halten - hoffe es ist mir gelungen.

```
public static void main(String[] s) {
	printNext(0, 5);
}
	
public static void printNext(int precessor, int limit) {
	int next = precessor +1;		// Berechne den Nachfolger
	if (next <= limit) { 			// wenn die Grenze noch nicht überschritten ist
		System.out.println(next);	// gib den Nachfolger aus
		printNext(next, limit);		// rufe die Methode mit dem ermittelten Nachfolger auf
	}
}
```


----------



## 0x7F800000 (29. Aug 2011)

sk72 hat gesagt.:


> Die nötige mathematische Grundkenntnisse besitze ich schon, nur weiß ich leider nicht genau wie ich es jetzt in Java umsetzen muss.


Ja, wie jetzt? Die Mathematische Definition hat Landei doch einfach nur wirklich 1:1 hingeschrieben, nur halt in java-style geklammert. Alles was bei der mathematischen Notation als

```
WERT falls PRÄDIKAT
```
da steht, wird ins englische übersetzt [falls = if, sonst = else], und dann einfach nur zu

```
if(PRÄDIKAT){ return WERT; }
```
verdreht und geklammert. Die Typen der Funktionen, die in der Mathematischen Notation als

```
f: X -> Y
```
hingeschrieben werden, übersetz man in Java so:

```
Y f(X x){ /* irgendwas vom typ Y zurückgeben */ }
```

Also wird die mathematische Definition

```
f: int -> long
f(n) := {
  n                    falls   n <= 1
  f(n-2) + f(n-1)  sonst
```
zu

```
long f(int n){
  if( n <= 1 ){
    return n;
  }else{
    return f(n-2) + f(n-1);
  }
}
```
ggf fügt man da noch das static-keyword hinzu, damit man keine Instanzen braucht, um die Methode aufzurufen... Was soll denn daran schwer sein?


> Ich stehe noch ganz am Anfang meines Studiums und dementsprechend besitze ich auch kaum Kenntnisse in Java.


Genau solche Beiträge halten mich immer wieder davon ab, mit einem Musikstudium anzufangen, obwohl ich nie ein Instrument aus der Nähe gesehen habe^^ 

Folgende Tipps: 
1) Leg dir deine persönliche Liste von Lieblingsprogrammen an, die du in zukunft bei jeder neuen "halbwegs general-purpose" - Sprache durchprogrammierst, etwa:
 - eine zahl ausgeben
 - zwei zahlen addieren und ausgeben
 - alle quadrate von 0 bis 100 ausgeben
 - fakultät berechnen
 - ein paar arrays / listen / maps / sets / matrizen anlegen, je nach dem was die bibliothek / sprache hergibt
 - mergesort implementieren
 - eingaben von der konsole einlesen, echo ausgeben

Wenn du dir viertel Stunde Zeit für sowas nimmst und es hinbekommst, dann kannst du dir sicher sein, dass du die minimal notwendigsten 10% der Sprache beherrschst, dich mit deinem Programm über die Konsole unterhalten, und somit beobachten kannst, was es so tut. Ab da läuft ales viel leichter, weil man ja sehen kann, was in der blöden Kiste passiert, danach ist es keine vollkommen finstere "Black-Box" mehr, und ab da kann man sich weiterentwickeln.

2) In den ersten 5 Semestern lernst in jedem Semester und in jeder Semesterpause jeweils eine andere Sprache. In deinem restlichen Studium lernst du alle 1.5 jahre eine neue Sprache. In deinem restlichen Leben lernst du alle 3 jahre eine möglichst grundlegend andersartige Sprache.


----------



## Sich (29. Aug 2011)

sk72 hat gesagt.:


> Es ging gerade um die Rekursion der natürlichen Zahlen {0,1,2,3,4,5 ... } und da sollte doch schon gelten: f(n) = f(n-1) + 1 ; f(0) = 0
> ?



Das ist so nicht richtig, gerade für die natürlichen Zahlen (inklusive 0) gilt f(n) = f(n-1) + f(n-2)! bsp; f(6) ist laut deiner Definition: f(6) = f(5)+1 = f(4)+1+ 1= f(3)+1+1+1 = f(2)+1+1+1+1 = f(1) 1+1+1+1+1 = 1+1+1+1+1+1 = 6 und das ist definitiv ungleich der allgemeinen Definition: f(6) = f(5) + f(4) = 8

Genau das stellt ja auch die Fibonacci-Folge dar: ein n-tes Glied der Folge ergibt sich aus der Addition der beiden vorgänger Glieder. vgl: Wikipedia:
Die Fibonacci-Folge ist eine unendliche Folge von Zahlen (den Fibonacci-Zahlen), bei der sich die jeweils folgende Zahl durch Addition ihrer beiden vorherigen Zahlen ergibt: 0, 1, 1, 2, 3, 5, 8, 13, …

Gruß
Sich


----------



## Fu3L (29. Aug 2011)

@Sich: Der TO spricht über das von jemand anderem ins SPiel gebrachte einfacherere Beispiel die Zahlen von 0 bis 10 auszugeben ohne Fibonacci. Das was er schrieb dazu, war richtig 
Es scheitert(e anfangs) ja vor allem an der Rekursion.


----------



## sk72 (29. Aug 2011)

Vielen Dank euch allen ! 

Die Aufgabe mit dem Fibonacci Algorithmus war die vorletzte Übung auf dem Aufgabenblatt, alle Anderen konnte ich ohne Probleme lösen. 

Ich werde mich vielleicht zunächst noch mit ein paar anderen Aufgaben intensiv(er) beschäftigen müssen, bevor ich auch diesen Algorithmus lösen kann.



> Leg dir deine persönliche Liste von Lieblingsprogrammen an, die du in zukunft bei jeder neuen "halbwegs general-purpose" - Sprache durchprogrammierst, etwa:



Japp, werde ich machen. 

Hier mal mein Code zu den Quadratzahlen, passt doch ? Jedoch gibt es bestimmt noch mehrere Codes die _schneller rechnen_, aber das sei mal für den Anfang uninteressant.


```
class quadrat{
	public static void main(String[] args) {
		
		int a = 0;
		int b = 0;
		
		while(a<=10) {

			if(a==b) {
			int c = a*b;
			System.out.println(c);
			a++;
			b++;
			}
		
		}
		
	}
	
}
```


Für die Fakultät werde ich auch mal noch versuchen einen Code zu schreiben, sollte mir doch hoffentlich gelingen.

Achja übrigens, sehr cooles Forum und nette User! Gefällt mir


----------



## Fu3L (29. Aug 2011)

Du könntest dir den Vergleich sparen  Wenn du immer beide um einen erhöhst, dann sind die beiden Zahlen doch eh immer gleich  Du köntnest es auch mit einer Zahl umsetzen^^ 
Aber sonst richtig


----------



## sk72 (29. Aug 2011)

Du hast natürlich recht, hier mal einen vernünftigen Code:


```
class quadrat{
    public static void main(String[] args) {    	
        int a = 0;       
        while(a<=10) {
        	int x = a*a;
        	System.out.println(x);
        	a++; 
            }
        }    
    }
```


----------



## 0x7F800000 (30. Aug 2011)

schon besser...

Für solche sachen wie "Variable initialisieren, solange inkrementieren wie etwas erfüllt ist" gibt es in java for-schleifen:

```
for(int a = 0; a < 100; a++) System.out.println(a * a);
```


----------



## Landei (30. Aug 2011)

Aber wolltest du das nicht _rekursiv_ lösen?


```
public class Square {

    public static int square(int x) {
        return sqrHelp(0, 1, x);
    }

    public static int sqrHelp(int s, int d, int x) {
        if (x == 0) {
            return s;
        } else {
            return sqrHelp(s + d, d + 2, x - 1); //der rekursive Aufruf
        }
    }

    public static void main(String[] args) {
        for(int i = 0; i < 20; i++)  {
            System.out.println(square(i));
        }
    }
}
```

Zusatzaufgabe: Finde die Multiplikation!


----------



## 0x7F800000 (30. Aug 2011)

Landei hat gesagt.:


> Aber wolltest du das nicht _rekursiv_ lösen?


@TO: Das nennst sich Humor, nur um das mal klarzustellen, kein Mensch würde das in wirklichkeit so schreiben 

Ich find's außerdem irgendwie doch noch zu lang, so geht's doch auch, wenn man nicht multiplizieren kann^^:

```
public static long square(int n){
		return n == 0 ? 0 : (square(n - 1) + n + n - 1);
	}
```


----------



## hape (15. Nov 2011)

... eine Haskell-Lösung wäre:


```
let fib=0:1:zipWith (+) fib (tail fib)
```

z.B. die ersten 10: 

```
take 10 fib
```
ergibt

```
[0,1,1,2,3,5,8,13,21,34]
```

;-) ... wie ginge das in Scala?

Gruß Hape


----------



## Landei (15. Nov 2011)

Erst mal die kanonische Haskell-Lösung:


```
fib = 0 : scanl (+) 1 fib
```

In Scala könnte man das nur mit Iteratoren oder Streams nachbauen, weil Scala-Listen strikt sind. Eine einfache Lösung wäre


```
def fib = Iterator.iterate((0,1)){case (x,y) => (y,x+y)}.map(_._1)

fib.take(10).toList
//--> List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
```

Deinen Code könnte man so übersetzen (was aber deutlich langsamer ist):

```
def fib:Stream[Int] = 0 #:: 1 #:: fib.zip(fib.tail).map(p => p._1 + p._2)
```

PS: Willkommen im Forum!


----------



## hape (16. Nov 2011)

Landei hat gesagt.:


> Erst mal die kanonische Haskell-Lösung:
> 
> 
> 
> ...


... das ist interessant. ich wußte gar nicht, dass man fib noch kürzer schreiben kann... das gefällt mir! Merci
Hape


----------

