Verständnis frage zu Rekursion
-
Ich habe hier ein kleines Programm das die fibonacci Zahl berechnet.
Was mir da bei nich klar ist, ist der Rechen vorgang von:
fibonacci(i-1) + fibonacci(i-2)
#include <stdio.h>
#include <limits.h>unsigned long fibonacci(unsigned int i) {
if (i<2) {
return i;
}
return fibonacci(i-1) + fibonacci(i-2);
}int main(void) {
unsigned int zahl;printf("Bitte eine positive ganze Zahl eingeben: ");
scanf("%u", &zahl);
printf("Die %u. Fibonaccizahl ist %lu\n",
zahl, fibonacci(zahl));
return 0;
}Schon mal Danke für die Hilfe!
-
Fahni schrieb:
Was mir da bei nich klar ist, ist der Rechen vorgang von:
und was genau ist nicht klar? Die technische Umsetzung oder die mathematische Definition?
-
Aha TU GRaz
!
-
Die mathematische Definition oder besser gesagt wie da bei die einzelnen rechen schrite aus sehen.
-
Mathematische definition:
fn = fn-1 + fn-2 n >= 2
Wenn du Fibonacci-Folge in google eingibst findest so manches!
-
Funktionsweise:
Fuer jede positive Zahl n > 1 wird die Summe der beiden kleineren n nach f(n)=f(n-1)+f(n-2) gebildet.
Fuer diese wiederum die Summe,
und wieder die Summe,
und wieder,
bis n<2: das Ergebnis ist bekannt.
Somit kann die Summe fuer f(2)= f(1)+f(0) gebildet werden,
daraus die Summe fuer f(3), ... f(n).
-
Ok sry mein Fehler!
@Fahni
ich würd mir die vorletzte VL-Präsentation von ESP anschauen da werden die einelnen Schritte eh genau gezeigt!!
-
hellihjb schrieb:
if (i<2) { return i; }Ist nicht ganz richtig da hier fibonacci(0)=0 waere (siehe Fibonacci-Folge).
das ist egal. alle folgen mit f(n)=f(n-1)+f(n-2) sind fibonacci-folgen. die startwerte sind frei. nicht vergessen, daß wikiblödia von privatleuten wie uns geschrieben wird und wir vergessen oft mal sachen.
spricht man vereinfachend von "der" fibonacci-folge, ist meistens eine gemeint mit den startwerten f(0)=undef f(1)=1 f(2)=1 oder f(0)=0 f(1)=1. und vereinfachend fibonacci-zahlen meint deren glieder.
-
OK Danke!!
Jetzt hab ichs verstande!