Seite 1 von 1

Rekursion

Verfasst: Mittwoch 4. Dezember 2019, 16:47
von wowlol
Hi liebe Python-Community!
Ich löse gerade folgende Aufgabe:
Schreiben Sie eine rekursive Funktion, die eine Liste von Zahlen L1 als Eingabe nimmt und eine Liste gleicher Länge L2 berechnet, die das kumulative Minimum enthält, nämlich das Element in L2 an der Position pos sollte dem kleinsten bisher gesehenen Element von L1 entsprechen (L1[0:pos+1]). Zum Beispiel,
min_c([3, 5, 2, 4, 7, 1, 5])
sollte zurückgeben: [3, 3, 3, 2, 2, 2, 2, 1, 1]

Mein Lösungsansatz ist bist jetzt:

Code: Alles auswählen

def min_c(L1):
    if len(L1)==2:
        if L1[0]<L1[1]:
            return [L1[0],L1[0]]
        else:
            return [L1[1],L1[1]]
      
    
    else:
        if L1[1]<L1[0]:
            L2=[L1[1]]+min_c(L1[1:(len(L1)+1)])
            return L2
        else:
            L2=[L1[0]]+min_c([L1[0]]+L1[2:(len(L1)+1)])
            return L2
Jedoch kommt bei mir folgendes Ergebnis beim Ausführen von min_c([3, 5, 2, 4, 7, 1, 5]) raus: [3, 2, 2, 2, 1, 1, 1]
Es liegt wohl daran, dass ich immer das zweite Element der Liste mit dem ersten vergleiche. Wie kann ich das ändern?

Vielen Dank und liebe Grüße,
Markus

Re: Rekursion

Verfasst: Mittwoch 4. Dezember 2019, 17:01
von __blackjack__
@wowlol: Als erstes mal hast Du ein Problem mit dem Rekursionsanker. ``c_min([])`` und ``c_min([42])`` funktionieren schon nicht. Das sind ja die beiden simplen Fälle die man erstes behandeln sollte. Und dann kann man sich im nächsten Schritt überlegen wie man das Problem von einer Liste mit n Elementen auf eine mit n-1 Elemente reduziert.

Edit: Ergebnisse gegenchecken lässt sich übrigens hiermit:

Code: Alles auswählen

In [22]: from itertools import accumulate                                       

In [23]: list(accumulate([3, 5, 2, 4, 7, 1, 5], min))                           
Out[23]: [3, 3, 2, 2, 2, 1, 1]
Edit 2: Dein ”korrektes” Beispiel ist demnach übrigens falsch.