Umkehr einer Liste (rekursiv)

[andi24]

Hallo zusammen,

ich möchte eine rekursive Funktion schreiben, die eine beliebige Liste komplett umkehrt. Leider fehlt mir dafür jeglicher Ansatz. Kann mir da jemand helfen? Bin noch Anfänger in Programmieren...

Vielen Dank, Andi

[Defnull]

Wozu? Sowas gibt es schon:

Code: Alles auswählen

>>> l=[1,2,3]
>>> l.reverse()
>>> l
[3, 2, 1]

Und Rekursion macht überhaupt keinen Sinn in diesem Zusammenhang, es sei denn du hast eine verschachtelte Liste.

Aber ich gehe mal davon aus, das es eine Hausaufgabe ist?

[Panke]

Eine umgekehrte Liste, ist das erste Element dieser Liste und davor die Umkehrung der Restliste.

[Gabelmensch]

Eine umgekehrte Liste, ist das erste Element dieser Liste und davor die Umkehrung der Restliste.

Verstehe ich jetzt nicht, ist doch das was Defnull geschrieben hat, oder?

[/me]

Eine umgekehrte Liste, ist das erste Element dieser Liste und davor die Umkehrung der Restliste.

Verstehe ich jetzt nicht, ist doch das was Defnull geschrieben hat, oder?

Ich glaube das war die Erklärung für eine mögliche Rekursion. Verwenden will man so etwas natürlich nicht.

[Defnull]

Eine umgekehrte Liste, ist das erste Element dieser Liste und davor die Umkehrung der Restliste.

Eher das letzte Element der Liste und danach die Restliste. Im Endeffekt das gleiche, macht aber mehr Sinn in der Implementierung.

[Panke]

Kommt auf die Implementierung der Liste an. Dass man sowas nicht macht, wenn es l.reverse() gibt, ist ja wohl klar. Aber es wurde nun mal direkt danach gefragt.

[andi24]

Hallo zusammen,

danke für euere schnellen Antworten! Ja, es geht tatsächlich um eine "Hausaufgabe", in der eben auch die Anwendung von Rekursionen geübt werden soll. Sonst hätte ich schon auch auf reverse() zurückgegriffen

Der Aufgabentext lautet lediglich: "Schreiben Sie eine rekursive Funktion zur kompletten Umkehr einer Liste!"

[jbs]

Eine umgekehrte Liste, ist das erste Element dieser Liste und davor die Umkehrung der Restliste.

Eher das letzte Element der Liste und danach die Restliste. Im Endeffekt das gleiche, macht aber mehr Sinn in der Implementierung.

Dann such dir einen Weg aus und probier es!

[Defnull]

Generelle Tipps für rekursive Programmierung:

Jeder Schritt muss dich näher ans Ziel bringen. Das heißt, das du in jeder Rekursionsstufe einen Teil des Problems lösen musst und nur den Rest rekursiv weiter reichen darfst. Tust du das nicht, wird das Problem nicht kleiner und die Rekursion läuft ewig.

Besonderes Augenmerk musst du auf die Terminierung richten, also den Fall, bei dem deine Funktion NICHT rekursiv sich selbst auf ruft, sondern ihr Teilproblem vollständig lösen kann. Ohne eine Terminierung würde die Funktion unendlich lange sich selbst aufrufen.

Du schreibst also eine Funktion, die einen Teil des Problems selbst löst und sich mit dem Resetproblem erneut (rekursiv) aufruft. Dann wird die eigene Lösung und der Rückgabewert des rekursiven Aufrufs kombiniert und zurück gegeben. Wenn es kein Resetproblem mehr gibt, sind wir fertig (terminiert) und geben nur das eigene Ergebnis zurück.

[EyDu]

Also in etwa so ^^:

Code: Alles auswählen

(lambda f: lambda x: f(f, x))(lambda f, x: x and f(f, x[1:])+[x[0]])

[Defnull]

Wir sind hier nicht bei lisp (und selbst ich hab Probleme, das da auf Anhieb zu verstehen O.o)

[Nocta]

Eine mögliche Lösung habe ich gerade mal geschrieben, aber es wäre ja zu einfach, wenn ich dir die jetzt posten würde
Darum hab ich mal die wichtigen Codestellen mit ??? ersetzt

Code: Alles auswählen

def reverse(L, i=0):
    if ???: # Abbruchbedingung
        return L # Die umgekehrte Liste zurückgeben
    else:
        ??? # Elemente schrittweise in umgekehrte Reihenfolge bringen
        return reverse(L, i+1)

Da hast du als Grundstruktur schon gegeben, dass sich i jedes mal um eins erhöht (und logischerweise damit die Abbruchbedingung zusammenhängt) und du in jedem Schritt L veränderst.
Dazu lösche ich die ursprünglichen Elemente von hinten angefangen und füge sie wieder ganz am Ende der Liste hinzu. (L.append() und L.pop() sind da praktische Funktionen)

Also sieht der Durchgang mit 3 Elementen wie folgt aus:

Code: Alles auswählen

i = 0:
L = [1, 2, 3] # 3 wurde gelöscht und wieder hinten angehangen (kein Effekt)

i = 1
L = [1, 3, 2] # 2 wurde gelöscht und wieder hinten angehangen

i = 2
L = [3, 2, 1] # 1 wurde gelöscht und wieder hinten angehangen

Der 1. (i=0) Schritt ist zwar unnötig, da er nichts verändert, aber der Code ist denke ich einfacher, wenn man den Fall nicht berücksichtigt.

Ich hoffe das hilft dir etwas mehr als EyDus Vorschlag

[Defnull]

Der i Parameter ist eigentlich überflüssig, es sei denn, in-place ist Bedingung Die Liste oder Teilliste ist alles, was man als Input braucht.

[DasIch]

Code: Alles auswählen

def reversed(l):
    if l:
        return [l.pop()] + reversed(l)
    return []

print reversed(range(3))

[Defnull]

@DasIch: Willst du unsere Bemühungen, dem OP etwas bei zu bringen, zur Nichte machen oder hast du einfach nur den Thread nicht gelesen?

Ganz abgesehen davon überschreibst du ein buildin. Böse!

[Nocta]

Der i Parameter ist eigentlich überflüssig, es sei denn, in-place ist Bedingung Die Liste oder Teilliste ist alles, was man als Input braucht.

i ist ja strenggenommen auch kein "Input", es soll ja nicht beim Aufruf übergeben werden, sondern nur innerhalb der Funktion überschrieben werden.
Es geht bestimmt auch ohne i, aber ich denke die Variante ist relativ verständlich (while-ähnlich) und kommt ohne kompliziertere Gedankenvorgänge aus.

[Leonidas]

Ich hoffe das hilft dir etwas mehr als EyDus Vorschlag

Also ich finde die Idee mit dem ``i`` jetzt nicht so sonderlich toll, um Rekursion zu verstehen. Zudem CPython keine Endrekursion optimiert bringt das ``i`` tatsächlich überhaupt nichts. Dadurch wird man eher durch irgendwelche Indexerei abgelenkt als durch die teilweise zerlegung in einfachere Probleme.

[andi24]

Vielen Dank für euere hilfreichen Antworten!! Mit dem Code von Nocta hab ich jetzt genau, was ich wollte...

Wobei mich der Interesse halber schon noch interessieren würde, wie die Lösung von EyDu arbeitet....der kann ich als Anfänger leider garnicht folgen

Vielen Dank euch allen und ein schönes Wochenende!!

[Hyperion]

Jeder Schritt muss dich näher ans Ziel bringen. Das heißt, das du in jeder Rekursionsstufe einen Teil des Problems lösen musst und nur den Rest rekursiv weiter reichen darfst.

Oder nach der Lösung das Ergebnis an die vorherige Rekursionsebene zurückliefern solltest (Wie beim Mergesort iirc). Gibt also zwei Möglichkeiten: Auf dem Weg in die Tiefe "Arbeit verrichten" (Qicksort) oder auf dem Weg zurück.