Fibonacci-Zahlen rekursiv
Verfasst: 27. Mär 2017 15:36
Hi !
Wir sitzen gerade am Korrektheitsbeweis zu den Fibonacci-Zahlen (rekursiv)
Wir haben die Invariante folgendermaßen definiert : Für k>=0 Rekursionsschritte sind die Fibonacci Zahlen für (0...k) korrekt gezählt/summiert. -->?
Nun die Uneinigkeit bezüglich des Induktionsschrittes:
Wir nutzen als Basis die Invariante und formulieren den IS folgendermaßen :
-Aufgrund der Induktionshypothese/Invariante müssen für k >=0 Rekursionsschritte die Fibonacci-Zahlen von 0...k korrekt gezählt werden. Damit diese Voraussetzung erfüllt wird, müssen die Fibonacci -Zahlen k-1 ebenfalls korrekt gezählt werden.
Dieser IS lässt uns vermuten, dass wir den Baum von unten nach oben Betrachten, also den Baum im Prinzip in seinem Endzustand betrachten, denn k>= Rekursionsschritte kann man ja nur korrekt berechnen , wenn fib(0) bzw. fib(1) aufgerufen werden.
Mathematisch gesehen macht dieser Induktionsschritt für uns Sinn.
Das Problem entsteht jedoch, wenn wir für den IS den rekursiven Code durchlaufen. Da sich in jedem Rekursionsschritt die Funktion neu aufruft, können wir gar nicht davon ausgehen , dass der unterste Teil des Fib.Baumes bereits ausgegeben wurde. So wissen wir gar nicht , ob auch k-1 Rekursionsschritten die Fib-Zahlen korrekt berechnet wurden, da der Baum noch gar nicht "so weit ist".
Ich hoffe , unser Problem ist einigermaßen zu verstehen. Im Prinzip (so haben wir das Gefühl) sehen wir einen großen Unterschied zwischen der mathematischen Funktionsweise des Baumes und die des Codes von oben nach unten .
Gruß
Wir sitzen gerade am Korrektheitsbeweis zu den Fibonacci-Zahlen (rekursiv)
Wir haben die Invariante folgendermaßen definiert : Für k>=0 Rekursionsschritte sind die Fibonacci Zahlen für (0...k) korrekt gezählt/summiert. -->?
Nun die Uneinigkeit bezüglich des Induktionsschrittes:
Wir nutzen als Basis die Invariante und formulieren den IS folgendermaßen :
-Aufgrund der Induktionshypothese/Invariante müssen für k >=0 Rekursionsschritte die Fibonacci-Zahlen von 0...k korrekt gezählt werden. Damit diese Voraussetzung erfüllt wird, müssen die Fibonacci -Zahlen k-1 ebenfalls korrekt gezählt werden.
Dieser IS lässt uns vermuten, dass wir den Baum von unten nach oben Betrachten, also den Baum im Prinzip in seinem Endzustand betrachten, denn k>= Rekursionsschritte kann man ja nur korrekt berechnen , wenn fib(0) bzw. fib(1) aufgerufen werden.
Mathematisch gesehen macht dieser Induktionsschritt für uns Sinn.
Das Problem entsteht jedoch, wenn wir für den IS den rekursiven Code durchlaufen. Da sich in jedem Rekursionsschritt die Funktion neu aufruft, können wir gar nicht davon ausgehen , dass der unterste Teil des Fib.Baumes bereits ausgegeben wurde. So wissen wir gar nicht , ob auch k-1 Rekursionsschritten die Fib-Zahlen korrekt berechnet wurden, da der Baum noch gar nicht "so weit ist".
Ich hoffe , unser Problem ist einigermaßen zu verstehen. Im Prinzip (so haben wir das Gefühl) sehen wir einen großen Unterschied zwischen der mathematischen Funktionsweise des Baumes und die des Codes von oben nach unten .
Gruß
).
