Seite 1 von 1
Endrekursion
Verfasst: Samstag 23. Januar 2016, 21:54
von henryfoster
Hallo,
ich habe in C ein kleines Programmbeispiel gefunden welches die Fibonaccifolge endrekursiv ausgibt mit hilfe von zwei Variabeln die als Akkumulator dienen, soweit ich das verstanden habe. Das Programm selbst funktioniert aber ich verstehe einfach nicht wie es arbeitet ^^
Man gibt die n-te Stelle der Fibonaccifolge ein und erhält die passende Zahl als Ausgabe.
1
Code: Alles auswählen
def fib_endrekursiv(n):
2 return fib_hilfe(n-1,1,0)
3
4def fib_hilfe(n, a , b):
5 if n <= 1:
6 return a + b
7 return fib_hilfe(n-1, b+a, a)
8print(fib_endrekursiv(5))
Ich kann auch keine Zwischenschritte ausprinten, da sofort die Fib-Zahl ausgegeben wird. Kann mir einer kurz erklären wie der Algorithmus arbeitet?
Meine Vermutung:
n, a , b
5-1,1,0
4-1,1,1
3-1,2,1
2-1,3,2
Re: Endrekursion
Verfasst: Samstag 23. Januar 2016, 21:58
von BlackJack
@henryfoster: Was genau verstehst Du denn nicht? Schreib Dir so einen Programmablauf einfach mal auf. Welche Werte haben die Variablen im jeweiligen Funktionsaufruf und wie kommt das Ergebnis dann zustande.
Edit: Und wieso kannst Du keine Zwischenschritte ausgeben? Du kannst doch die Werte bei jedem rekursiven Aufruf ausgeben lassen‽
Re: Endrekursion
Verfasst: Samstag 23. Januar 2016, 22:19
von henryfoster
Meine Vermutung:
n, a , b
5-1,1,0
4-1,1,1
3-1,2,1
2-1,3,2 und 3 +2 ist 5 ! haha
Python kommt auf die gleichen Ergebnisse wie mein Kopf^^ Hat etwas gedauert aber letzten Endes hab ichs doch begriffen und mein Kaffee ist kalt geworden
Ja jetzt hab ich es gebacken bekommen mit dem auslesen.Ich hatte den Printbefehl falsch eingerückt.
Re: Endrekursion
Verfasst: Sonntag 24. Januar 2016, 11:18
von henryfoster
Eine Frage habe ich aber doch noch.
Was für mich total unlogisch klingt ist folgendes:
Code: Alles auswählen
def exp(n):
if n == 0:
return 1
else:
return 2 * exp(n-1)
print(exp(5))
Ablauf: 2*exp(2*exp(2*exp(2*exp(2*exp(0)))))
Sobald n 0 erreicht wird 1 wiedergegeben(Zeile3) aber ich verstehe nicht warum 1? b.z.w. warum wird 32 ausgegeben und nicht 1 und warum bekomme ich 0 als Ergebnis wenn ich diese 1 zu einer 0 ändere?
Re: Endrekursion
Verfasst: Sonntag 24. Januar 2016, 11:46
von Liffi
henryfoster hat geschrieben:
print(exp(5))
Ablauf: 2*exp(2*exp(2*exp(2*exp(2*exp(0)))))
Das wäre ein bisschen viel.
Eigentlich passiert eher sowas:
exp(5) = 2*exp(4)
2*exp(4) = 2*2*exp(3)
...
2*2*2*2*2*exp(0).
exp(0) gibt ja 1 aus, dann steht also:
2*2*2*2*2*1 = 32.
Sobald n 0 erreicht wird 1 wiedergegeben(Zeile3) aber ich verstehe nicht warum 1? b.z.w. warum wird 32 ausgegeben und nicht 1 und warum bekomme ich 0 als Ergebnis wenn ich diese 1 zu einer 0 ändere?
Wenn du die 1 in eine 0 verwandelst, steht in der Multiplikation eine 0. Wenn man mit 0 multipliziert kommt 0 raus.
Re: Endrekursion
Verfasst: Sonntag 24. Januar 2016, 11:54
von BlackJack
Ausserdem ergibt 2⁰ ja auch 1: