proggen.org

Verfasst: **Sa Aug 30, 2014 3:43 pm**

#include<stdio.h>

int fib (int n);

int main()
{
	int index=1;
	
	while(index<=40)
	{
		printf("fib(%d) -> %d\n",index,fib(index));
		index++;
	}
	return 0;
}

int fib (int n)
{
	if(n<2)
		return n;
	
	return fib(n-1)+fib(n-2);
}

Code: Alles auswählen

#include<stdio.h>

int main ()
{
	int n1=1,n2=1;
	
	printf("%d\n%d\n",n1,n2);

for (int i=0; i<20 ; i++){
	n1=n1+n2;
	n2=n1+n2;

	printf("%d\n%d\n",n1,n2);
	}
return 0;
}

2 Fragen:
ich hebe mir zu der fibonaccireihe ein paar gedanke gemacht und bin somit zum 2. code gekommen welcher kürzer und schneller ist als der im tutorial
jetzt frage ich mich wo der der vorteil im ersten code liegt und
2. wieso der 1. so viel länger dauert und wie dieser genau arbeitet und wieso er funktioniert(ich glaube das erklärt sich gegenseitig)

Code: Alles auswählen

int fib (int n)
{
   if(n<2)
      return n;
   
   return fib(n-1)+fib(n-2);
}

wenn fib vom aufrufer zB den wert 5 bekommt wird dann bei

Code: Alles auswählen

return fib(n-1)+fib(n-2);

Code: Alles auswählen

return fib(4)+fib(3);

berechnet und dann der fib von 3 und 4 und dann fib von 3 und 2 und 2 und 1 -> 2 1 1 0 1 0 1 -> 1 0 1 1 0 1 0 1
fib(5) = 5

bei 6 -> 5 4 -> 4 3 3 2 -> 3 2 2 1 2 1 1 0 -> 2 1 1 0 1 0 1 1 0 1 1 0 -> 1 0 1 1 0 1 0 1 1 0 1 1 0
fib (6) = 8 also...

bin mir nicht ganz sicher ob es genau so funktioniert aber es kommt auf jeden fall immer das richtige raus

ruft die funktion sich solange selbst auf bis sie nur noch aus 0en und 1en besteht die sie laut fib ohne weitere überarbeitung zurückgeben werden müssen und die werden dann am ende zusammengerechnet?

Danke im Voraus

Verfasst: **Sa Aug 30, 2014 4:09 pm**

Das nennt sich Rekursion. Wenn du dir den Stacktrace anguckst, sieht das etwa so aus:

Code: Alles auswählen

main()
+fib(6)
++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)
++fib(4)
+++fib(3)
++++fib(2)
+++++fib(1)
+++++fib(0)
++++fib(1)
+++fib(2)
++++fib(1)
++++fib(0)
+printf()

Du siehst, fib wird oft mit gleichen Argumenten aufgerufen. Deshalb ist die rekursive Lösung für Fibonnacci so ineffizient. Außerdem bringt jeder Funktionsaufruf etwas Overhead mit sich und die Rekursionstiefe ist durch den Speicher ebenfalls begrenzt.

Die Addition wird immer nach Rückkehr der beiden Funktionsaufrufe ausgeführt. Dass es immer bis 1 und 0 geht liegt an der Abbruchbedingung "if (n<2) return n;"

Vorteil der rekursiven Lösung ist, dass es sehr der mathematischen Definition gleicht und deshalb einfach implementiert werden kann. Der Schritt von rekursiver Funktion zu iterativer Funktion ist nicht immer trivial und erfordert deshalb mehr Wissen und Können.

Verfasst: **Sa Aug 30, 2014 11:26 pm**

ich bin mit c noch nicht besonders vertraut also kann ich mir auch under Stacktrace noch nichts vorstellen^^
liege ich mit dem ablauf der funktion richtig?

LG

Verfasst: **So Aug 31, 2014 2:35 pm**

AlexImperator hat geschrieben:ich bin mit c noch nicht besonders vertraut also kann ich mir auch under Stacktrace noch nichts vorstellen^^
liege ich mit dem Ablauf der funktion richtig?

Das ist keine Frage von C oder irgendeiner Programmiersprache. Das ist Programmierung, die Du mit der Sprache C formulieren kannst. Das Konzept nennt sich Rekursion, was soviel aussagt, wie dass sich etwas selbst aufruft. Wie ein Traum in dem Du träumst aufwachst zu sein und glaubst geträumt zu haben. Dann hattest Du einen Traum innerhalb eines Traumes. ^^

AlexImperator hat geschrieben:wenn fib vom aufrufer zB den wert 5 bekommt wird dann bei
Code: Alles auswählen
return fib(n-1)+fib(n-2);
Code: Alles auswählen
return fib(4)+fib(3);
berechnet und dann der fib von 3 und 4 und dann fib von 3 und 2 und 2 und 1 -> 2 1 1 0 1 0 1 -> 1 0 1 1 0 1 0 1
fib(5) = 5

Genau.

Und weil der soviel rechnen muss - und im Prinzip immer nur irgendwas plus 1 rechnet, dauert das entsprechend lang.

AlexImperator hat geschrieben:bin mir nicht ganz sicher ob es genau so funktioniert aber es kommt auf jeden fall immer das richtige raus
ruft die Funktion sich solange selbst auf bis sie nur noch aus 0en und 1en besteht die sie laut fib ohne weitere Überarbeitung zurückgeben werden müssen und die werden dann am ende zusammengerechnet?

Nicht am Ende... immer wieder. Da steht ja fib(n-1) PLUS fib(n-2)

Erstmal klingt Rekursion hier merkwürdig. Aber genauso ist diese Reihe definiert. Man kann die mathematische Vorgabe 1:1 umsetzen und das klappt - dauert aber. Iterativ arbeiten Computer oft schneller. Wenn Du aber ein Labyrinth erkundest, dann läufst Du an einer Kreuzung erstmal nach links bis Du eine Sackgasse erreichst, dann nach vorne und dann nach rechts. Und wenn Du den Ausgang gefunden hast, rufst Du halt Juhu. Dieses Vorgehen nennen wir mal "BearbeiteKreuzung()". Wenn Du aber statt einer Sackgasse eine Kreuzung erreichst, dann machst Du das gleiche wie zuvor: erst links, dann mitte, dann rechts... Die Handlungsfolge ist identisch... also machst Du wieder BearbeiteKreuzung(). Das Problem wiederholt sich. Ganz am Schluss, schreist Du Juhu und die Funktion wird verlassen und kehrt in die rufende Funktion zurück. Die ruft auch "Juhu" und beendet sich... die Rekursion wird wieder abgebaut.
Das Juhu bei Fibunacci ist das

Code: Alles auswählen

if(n<2)
      return n;

Fachmännisch "Rekursionsanker" genannt.

Verfasst: **So Aug 31, 2014 8:24 pm**

Xin hat geschrieben: Nicht am Ende... immer wieder. Da steht ja fib(n-1) PLUS fib(n-2)

Wie genau geht das dann?

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

wie kann das programm den zusammenrechenen bevor er eine 1 errechnet hat

6
5 -> 4 3 -> 3 2 2 1 -> 2 1 1 0 1 0 1 -> 1 0 1 1 0 1 0 1 = 5
4 -> 3 2 -> 2 1 1 0 -> 1 0 1 1 0 ..............................= 3
5+3=8

oder

6
5 -> 4 3
.4 -> 3 2
..3 -> 2 1
...2 -> 1 0
...1 -> 1
..2 -> 1 0
.3 -> 2 1
..2 -> 1 0
.1 -> 1
4 -> 3 2
.3 -> 2 1
..2 -> 1 0
..1 -> 1
.2 -> 1 0
output erg. fib(6)

(war zwar ein bisschen arbeit, aber wenn man schon mal angefangen hat muss man es auch zu ende bringen^^)

so arbeitet das programm genau vermute ich
und immer wenn er eine neue 1 findet addiert der die oder?

so ist:

Xin hat geschrieben: Nicht am Ende... immer wieder. Da steht ja fib(n-1) PLUS fib(n-2)

gemeint

bei den anderen zwei wegen arbeitet man nicht wie das programm?

Verfasst: **So Aug 31, 2014 9:06 pm**

ich bin mit c noch nicht besonders vertraut also kann ich mir auch under Stacktrace noch nichts vorstellen^^
liege ich mit dem ablauf der funktion richtig?

Hier sind noch zwei weitere "klassische" Rekursionsprobleme: die Berechnung der Fakutät einer Zahl (!N):
https://www.youtube.com/watch?v=Mv9NEXX1VHc ,schön in einzelnen Schritten durchgekaut.
Und die Türme von Hanoi. Vielleicht ist das ja was für Dich.
Ich finde den "Computerphile"-Youtubekanal insgesamt recht interessant, doch wirklich empfehlenswert sind die Schwesterkanäle "Numberphile" für Mathe und "Sixty Symbols" für Physik.

Verfasst: **Mo Sep 01, 2014 7:53 am**

Sehr schön erklärt....

Wie war das, wer Rekursion verstehen will, der muss zuerst Rekursion verstehen...

Verfasst: **Mo Sep 01, 2014 8:55 am**

AlexImperator hat geschrieben:
Xin hat geschrieben: Nicht am Ende... immer wieder. Da steht ja fib(n-1) PLUS fib(n-2)
Wie genau geht das dann?

Im Prinzip, wie Du das beschreibst. Es wird 0 und 1 addiert und an anderer Stelle wird nochmal 0+1 addiert. Das ist die unterste Ebene der Funktionsaufrufe - da wo n<2 ist.
Diese Werte werden zurückgegeben und dann wird irgendwo 1+1 addiert und 2 zurückgegeben. So addieren sich immer größer werdende Zahlen...

AlexImperator hat geschrieben:(war zwar ein bisschen arbeit, aber wenn man schon mal angefangen hat muss man es auch zu ende bringen^^)

So sieht der Computer das auch... darum dauert die rekursive Variante hier auch so lange... ^^

AlexImperator hat geschrieben:so arbeitet das programm genau vermute ich
und immer wenn er eine neue 1 findet addiert der die oder?

Nein, er sucht nicht. Er addiert einfach. Ich packe mal [] um jeden Funktionsaufruf und für jede erfolgte Addition nehme ich ()

Code: Alles auswählen

fib(4) = [ fib(3) ] + [ fib(2) ]
fib(4) = [ [ fib(2) ] + [ fib(1) ] ] + [ [ fib(1) ] + [ fib(0) ] ]
fib(4) = [ [ [ fib(1) ] + [ fib(0) ] ] + [ fib(1) ] ] + [ [ fib(1) ] + [ fib(0) ] ]
fib(4) = [ [ [ 1 ] + [ 0 ] ] + [ 1 ] ] + [ [ 1 ] + [ 0 ] ]
Addieren wir mal:
fib(4) = [ [ (1) ] + [ 1 ] ] + [ (1) ]
Zwei Additionen hätten wir schonmal.
fib(4) = [ (2) ] + [ (1) ]
Drei... hierbei werden jetzt auch größere Zahlen addiert, die sich aus den vorherigen Additionen gebildet haben.
fib(4) = [ (3) ]
Vier und jetzt erst steht das Eregbnis bereit.

AlexImperator hat geschrieben:bei den anderen zwei wegen arbeitet man nicht wie das programm?

Wichtig ist, dass jeder Funktionsaufruf eine eigene Addition bewirkt. Es werden nicht die 1er gesammt und dann gezählt, sondern jeder Aufruf berechnet irgendwas aus dem, was die anderen Funktionsaufrufe zurückgegeben haben. Nur fib(0) und fib(1) berechnen nix, sondern geben einfach den Wert zurück.

Man kann die Fibunacci-Reihe so ausrechnen, wie sie mathematisch vorgegeben ist. Aber das bedeutet, dass der Computer die kleineren Fibunacci-Zahlen immer wieder neu berechnet. Und damit wird das ganze sehr zeitaufwendig, weil die Reihe sehr schnell, sehr groß wird und diese großen Zahlen sich im Prinzip dadurch zusammen setzen, dass oft 0 und 1 addiert werden, bevor da größere Zahlen draus werden.

nouseforname hat geschrieben:Wie war das, wer Rekursion verstehen will, der muss zuerst Rekursion verstehen...

Ist auch bei proggen.org eindeutig beschrieben:

Glossar: Rekursion

Verfasst: **Mo Sep 01, 2014 1:47 pm**

Man kann auch mit Rekursion einen Cache für bereits berechnete Werte benutzen. Dann läuft das in etwa so (Pseudocode):

Code: Alles auswählen

int fib(int x) {
   if (x not in fib_cache)
      fib_cache[x] = fib(x-1) + fib(x-2);
   return fib_cache[x];
}

0 und 1 müssen dann beim Anlegen des fib_cache schon eingefügt werden. Da immer zuerst einer der Summanden und dann erst der andere Summand ausgewertet wird, sollte fib(x-2) bereits im Cache stehen, wenn es aufgerufen wird.

proggen.org

[C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

[C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

Re: [C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

Re: [C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

Re: [C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

Re: [C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

Re: [C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

Re: [C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

Re: [C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|

Re: [C] Fibonacci-Reihe im Detail |[ fib(n-1)+fib(n-2) ]|