Seite 1 von 1
Rekursion/Liste
Verfasst: Sonntag 19. November 2017, 10:38
von momo9945
Hey Leute, leider habe ich bei der folgenden Aufgabe Probleme:
"Schreiben Sie eine Funktion fib(n), welche die ersten n Fibonacci-Zahlen in einer Liste zurückgibt, wobei n∈ℕ
gilt. Die i-te Fibonacci-Zahl lässt sich mithilfe der folgenden Formel berechnen:
fib(i)= falls i =1 --> 1
falls i=2 --> 1
sonst fib(i−1)+fib(i−2) "
Naja das ganze soll mit hilfe einer rekursiven Funktion geshrieben werden. Mein Ansatz waere folgendes gewesen:
Code: Alles auswählen
def fib(i):
L=[]
if i == 1:
return L.append(1)
elif i == 2:
return L.append(1)
else:
return L.append(fib(i-1)+fib(i-2))
jedoch kommen hierbei nur verschachtelte listen raus (was ja auch logisch ist). Deshalb wollte ich fragen, ob jemand so lieb waere, mir evntl. einen denkanstoss zu geben
Danke:)
Re: Rekursion/Liste
Verfasst: Sonntag 19. November 2017, 10:53
von Liffi
Gibt append überhaupt was zurück?
Ansonsten wäre ein erster Ansatz, die Liste einfach beim Aufruf mitzugeben, dann kann sie auch weiter befüllt werden.
Re: Rekursion/Liste
Verfasst: Sonntag 19. November 2017, 11:12
von __deets__
Du mischst hier zwei Dinge: ein Fibonacci-Zahl berechnen, und mehrere Werte in eine Liste speichern. Ich würde das trennen, und dann wird die Aufgabe trivial.
Effizienter wird es natürlich wenn man wie von liffi vorgeschlagen einen Akkumulator mitgibt. Dann kannst du Werte die du schon mal berechnet hast einfach nachschlagen.
Re: Rekursion/Liste
Verfasst: Sonntag 19. November 2017, 11:53
von momo9945
Liffi hat geschrieben:Gibt append überhaupt was zurück?
Ansonsten wäre ein erster Ansatz, die Liste einfach beim Aufruf mitzugeben, dann kann sie auch weiter befüllt werden.
__deets__ hat geschrieben:Du mischst hier zwei Dinge: ein Fibonacci-Zahl berechnen, und mehrere Werte in eine Liste speichern. Ich würde das trennen, und dann wird die Aufgabe trivial.
Effizienter wird es natürlich wenn man wie von liffi vorgeschlagen einen Akkumulator mitgibt. Dann kannst du Werte die du schon mal berechnet hast einfach nachschlagen.
okay danke euch, werde das gleich mal ausprobieren
Re: Rekursion/Liste
Verfasst: Sonntag 19. November 2017, 12:18
von Sirius3
Eigentlich widersprechen sich die Anforderungen. Wenn ich die ersten n Fibonacci-Zahlen berechnen will, brauche ich keine Rekursion, weil ich schon eine iterative Lösung habe. Aus einem schönen O(n)-iterativen Problem mache ich ein häßliches O(n)-Rekursionsproblem, oder ein O(N^2)-Rekusionsproblem.
@momo9945: aus Deinem gezeigten Code kommen nur None oder TypeError heraus, weil man None-Werte nicht addieren kann. Du mischst zwei Teile der Aufgabe, das Berechnen der Zahlen und das Erzeugen der Liste.
Für ersteres würde man einen Iterator schreiben und Zweiteres mit islice und list lösen:
Code: Alles auswählen
def iter_fibonacci(a=1, b=1):
while True:
yield a
a, b = b, a+b
N = 100
numbers = list(islice(iter_fibonacci(), N))