Endrekursion

[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

[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‽

[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.

[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?

[Liffi]

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.

[BlackJack]

Ausserdem ergibt 2⁰ ja auch 1:

Code: Alles auswählen

In [1]: 2**0
Out[1]: 1