Rechtsrekursive Liste

[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!

[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.

[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:

Code: Alles auswählen

for i in range(1, len(liste)+1, -1):

Aber was kommt dann in der Schleife? Mein erster Gedanke war sowas hier:

Code: Alles auswählen

liste_neu = [liste[-i], liste[-i+1]]

Aber das funktioniert nicht wirklich... Könntest du mir noch ein paar Tipps geben?

[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.

[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.

[LeSchakal]

@NPC

Wenn ich mich richtig erinnere, ist deine Beispielsfunktion fak() linksrekursiv.

[NPC]

Ach Mist,
Ich bin blöd Sorry.

Danke für den Hinweis LeSchakal

[__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()