Seite 1 von 1
Rechtsrekursive Liste
Verfasst: Montag 25. Mai 2020, 15:58
von Collin
Hallo!
Ich sitze schon seit Stunden an dieser Aufgabe für die Uni und verzweifele langsam daran... Wir sollen aus einer normalen, unverschachtelten Liste eine rechtsrekursive Liste der Länge 2 machen.
Beispiel: [1, 2, 3] soll zu [1, [2, [3]]] werden.
Ich habe es erstmal so versucht...
Code: Alles auswählen
liste = [1,2,3]
liste1 = [liste[-1]]
liste2 = [liste[-2], liste1]
liste3 = [liste[-3], liste2]
...aber erstens soll die Lösung rekursiv sein (und das ist meine ja nicht) und zweitens funktioniert meine Lösung nur für Listen der Länge 3. Hat jemand eine Idee, wie ich das Problem lösen könnte?
Vielen Dank schon mal im Voraus!
Re: Rechtsrekursive Liste
Verfasst: Montag 25. Mai 2020, 16:34
von Sirius3
Bei Rekursion brauchst Du erst ein Rekursionsende: wie sieht das aus?
Und dann einen Rekursionsschritt, wie sieht der aus?
Und dann packst Du das ganze in eine Funktion, die sich selbst mit den angepassten Parametern aufruft.
Re: Rechtsrekursive Liste
Verfasst: Montag 25. Mai 2020, 16:59
von Collin
Danke für die schnelle Antwort!
Also mein Rekursionsende ist len(liste)+1 ("+1" damit die Länge der Liste mit inbegriffen ist). Und der Rekursionschritt ist 1 (beziehungsweise -1, weil ich ja bei der Länge der Liste anfangen muss). Also müsste die Schleife so aussehen:
Aber was kommt dann in der Schleife? Mein erster Gedanke war sowas hier:
Aber das funktioniert nicht wirklich... Könntest du mir noch ein paar Tipps geben?
Re: Rechtsrekursive Liste
Verfasst: Montag 25. Mai 2020, 17:22
von Sirius3
Eine Schleife über einen Index ist in Python meist falsch. Für eine rekursive Funktion darf es auch gar keine for-Schleife geben.
Ihr habt doch sicher in der Vorlesung schon andere Beispiele für Rekursion behandelt. Schau nochmal nach, was dort mit Rekursionsende und -schritt gemeint ist.
Re: Rechtsrekursive Liste
Verfasst: Dienstag 26. Mai 2020, 15:22
von NPC
Hallo Collin,
deine Lösung momentan ist nicht rekursiv. Ein Beispiel für eine rekursive Funktion wäre:
Code: Alles auswählen
def fak(n):
# Hier ist die Abbruch bedinung (wenn 1, dann return 1)
if n == 1:
return 1
else:
# Und hier der Rekursionsschritt
return fak(n-1) * n
Manchmal kann man das zwar auch interativ Lösen:
Code: Alles auswählen
def fak(n):
prod = 1
for i in range(1, n+1):
prod *= i
return prod
aber beide haben eine unterschiedliche Struktur.
Versuche also erstmal wie bereist von Sirius gesagt die beiden Bedingungen zu formulieren.
Re: Rechtsrekursive Liste
Verfasst: Donnerstag 28. Mai 2020, 17:14
von LeSchakal
@NPC
Wenn ich mich richtig erinnere, ist deine Beispielsfunktion fak() linksrekursiv.
Re: Rechtsrekursive Liste
Verfasst: Donnerstag 28. Mai 2020, 17:28
von NPC
Ach Mist,
Ich bin blöd
Sorry.
Danke für den Hinweis LeSchakal
Re: Rechtsrekursive Liste
Verfasst: Donnerstag 4. Juni 2020, 13:13
von __blackjack__
Hab es mal in C implementiert, wobei das nicht so ganz nach C aussieht, wegen der libCello, die ich da verwende:
Code: Alles auswählen
#include "Cello.h"
var unflatten(var items) {
if (len(items) < 2) {
return items;
} else {
var tail = copy(items);
pop_at(tail, $I(0));
return new(Tuple, get(items, $I(0)), unflatten(tail));
}
}
int main(int argc, char** argv) {
var test_cases = new(Array, Tuple,
tuple($I(1), $I(2), $I(3)),
tuple($I(1), $I(2)),
tuple($I(1)),
tuple()
);
foreach (test_case in test_cases) {
println("%$", unflatten(test_case));
};
return 0;
}
Ausgabe:
Code: Alles auswählen
tuple(1, tuple(2, tuple(3)))
tuple(1, tuple(2))
tuple(1)
tuple()