Rekursion/Liste

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
momo9945
User
Beiträge: 2
Registriert: Sonntag 19. November 2017, 10:27

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:)
Liffi
User
Beiträge: 153
Registriert: Montag 1. Januar 2007, 17:23

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__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

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.
momo9945
User
Beiträge: 2
Registriert: Sonntag 19. November 2017, 10:27

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
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

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))
Antworten