Umkehr einer Liste (rekursiv)

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

[jbs]

inplace mit Vertauschen

Code: Alles auswählen

def reverse(seq, i=0):
    if i < len(seq)/2:
        seq[i],seq[-(i+1)] = seq[-(i+1)], seq[i]
        reverse(seq, i+1)

[Defnull]

Na jetzt ist es ja eh offen. Meine Lösung wäre gewesen:

Code: Alles auswählen

def stupidhomework(l):
  return l[-1:] + stupidhomework(l[0:-1]) if l else []

[EyDu]

Aber natürlich darf bei so etwas reduce nicht fehlen:

Code: Alles auswählen

reduce(lambda xs, x: [x]+xs, [1,2,3], [])

@Defnull: Deine ist quasi meine Lösung. Nur von der anderen Richtung und if/else statt einem and.

[cofi]

Na dann packen wir noch Scheme dazu

Code: Alles auswählen

(define (reverse alist)
    (foldl cons '() alist))

[Leonidas]

Ist die Frage wo dann eure Lösungen rekursiv sind. Und nein, ich lasse bei ``fold`` nicht gelten dass es ja rekursiv sein könnte

[EyDu]

Und nein, ich lasse bei ``fold`` nicht gelten dass es ja rekursiv sein könnte

Ich schon

[HWK]

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

Schlimmer noch: Er "löscht" die Ausgangsliste.

Code: Alles auswählen

>>> l
[0, 1, 2]
>>> reversed(l)
[2, 1, 0]
>>> l
[]

MfG
HWK

[HWK]

Und Haskell:

Code: Alles auswählen

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

MfG
HWK

[DasIch]

Schlimmer noch: Er "löscht" die Ausgangsliste.

Das lässt sich ja dokumentieren.

[bords0]

Divide-and-conquer darf natürlich nicht fehlen!

Code: Alles auswählen

def f(a):
    if len(a) > 1:
        m = len(a) / 2
        return f(a[m:]) + f(a[:m])
    return a

[lunar]

Ocaml:

Code: Alles auswählen

let rec reverse = function
  | [] -> []
  | x :: xs -> (reverse xs) @ [x]

[jbs]

Das ist das was ich an so einem Thread mag!

[Defnull]

Divide-and-conquer darf natürlich nicht fehlen!

Code: Alles auswählen

def f(a):
    if len(a) > 1:
        m = len(a) / 2
        return f(a[m:]) + f(a[:m])
    return a

Die bisher coolste Lösung finde ich.

[numerix]

Divide-and-conquer darf natürlich nicht fehlen!

Code: Alles auswählen

def f(a):
    if len(a) > 1:
        m = len(a) / 2
        return f(a[m:]) + f(a[:m])
    return a

Die bisher coolste Lösung finde ich.

Ja, gefällt mir auch gut. Ließe sich auch so schreiben:

Code: Alles auswählen

f = lambda a: f(a[len(a)/2:])+f(a[:len(a)/2]) if len(a)>1 else a

[derdon]

Ocaml:

Code: Alles auswählen

let rec reverse = function
  | [] -> []
  | x :: xs -> (reverse xs) @ [x]

Danke für die Lösung. Ich war schon am verzweifeln, weil ich immer das hier versucht habe: [...]

Edit: Ich merke grade, dass meine Versuche noch viel schlimmer waren. Die behalte ich doch lieber für mich...