Umkehren einer Liste mit Rekursion in Python

Question

def revlist(lst): 
    if len(lst) == 1: 
     return lst 
    else: 
     return lst[(len(lst) - 1) 

Ich bin so weit gekommen, aber ich weiß nicht, was ich als nächstes tun soll. Ich übe Rekursion für meine Prüfungen. Wenn jemand helfen könnte, wäre ich dankbar.

Answer 1

Im Basisfall haben Sie keine Liste, daher möchten Sie die leere Liste zurückgeben.

Rekursive Fall ist, dass Sie tun, so dass Sie das letzte Element an den rekursiven Aufruf auf den Rest der Liste voranzustellen.

def revlist(lst): 
    if not lst: 
     return lst 
    # Create a list containing only the last element 
    last = [lst[-1]] 
    # Rest contains all elements up to the last element in `lst` 
    rest = lst[:-1] 
    # Prepend last to recursive call on `rest` 
    return last + revlist(rest) 

Hier ist ein Fahrer, den ich schrieb:

lst = [1, 2, 3, 4, 5] 
print(revlist(lst)) 

Dies ergab:

12:03 $ python test.py 
[5, 4, 3, 2, 1] 

Dieses mit allen Iterables arbeiten.

Answer 2

Denken Sie an das, was Sie bei jedem rekursiven Aufruf erreichen möchten. Der Link, den thefourtheye in seinem Kommentar erwähnt zeigt ein wirklich gutes Beispiel dafür, wie man eine Liste mit Rekursion Summe:

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6]) 
         = 1 + (3 + listSum([4, 5, 6])) 
         = 1 + (3 + (4 + listSum([5, 6]))) 
         = 1 + (3 + (4 + (5 + listSum([6])))) 
         = 1 + (3 + (4 + (5 + (6 + listSum([]))))) 

dies als Basispunkt verwenden, wie würden Sie dann eine umgekehrte Liste erreichen? Es würde wahrscheinlich so etwas wie aussehen:

revlist([1, 3, 4, 5, 6]) = [6] + revlist([1, 3, 4, 5]) 
         = [6] + ([5] + revlist([1, 3, 4])) 
         = etc etc 
         = [6] + ([5] + ([4] + ([3] + ([1] + revlist([]))))) 

Dies zeigt dann genauer, was Sie erreichen möchten. Am Ende würden Sie das bekommen.

def revlist(lst): 
    if not lst: 
     return [] 
    else: 
     return lst[-1:] + revlist(lst[:-1]) 

Answer 3

Ihr einfacher Fall ist in Ordnung, wenn die Länge der Liste 1 (oder kleiner) ist, einfach die Liste zurückgeben. In der Tat können wir einfach überprüfen, ob die Liste leer ist (durch Ausgabe von if not lst). Wenn die Liste größer ist, müssen Sie darüber nachdenken, wie Sie das Problem im rekursiven Fall vereinfachen können. In Worten, Sie können es so formulieren: Wenn die Liste länger als 1 ist, geben Sie mir das letzte Element der Liste um die Liste erweitert, die ich bekomme, wenn ich die angegebene Liste ohne das letzte Element umkehren. Die letztere Liste ist um eins kleiner als die ursprüngliche Liste, wodurch das Problem vereinfacht wird.

In Code:

def reverse(lst): 
    if not lst: # this will be true if lst == [] 
     return lst 
    return lst[-1:] + reverse(lst[:-1]) # recursive case 

# Demo 
print(reverse([1,2,3,4,5])) # [5, 4, 3, 2, 1] 

Answer 4

eine andere Art und Weise

def revlist(lst): 
    if len(lst) == 0: 
     return ([]) 
    else: 
     return (revlist(lst[1:]) + [lst[0]]) 

Answer 5

Eine Version mit der Idee einer Funktion Wir brauchen

fold geschrieben, dass wir Nachteile nennen (Dies kommt von Lisp/Schema usw.). Es nimmt ein Element und eine Liste und fügt dieses Element dem Kopf (Start) der Liste hinzu. Beachten Sie, dass dies in Python nicht effizient ist.

def cons(x,xs): 
    return [x] + xs 

Nun wird die Funktion Falte (streng nach links falten gesprochen). Dies ist eine Funktion in eigener Sache und kann für viele Dinge verwendet werden (siehe den Link) das Python-Äquivalent wäre wahrscheinlich reduce.Beachten Sie, dass es eine Funktion nimmt f und wendet diese Funktion auf den Kopf der Liste und der variablen acc (kurz für Akkumulator)

def foldl(f,acc,xs): 
    if not xs:   
    return acc 
    head, *tail = xs 
    return foldl(f, f(head,acc), tail) 

Jetzt können wir eine Version von Reverse schreiben, die rekursiv ist (weil fache rekursiv)

def reverse(xs): 
    return foldl(cons, [], xs) 

Also eine Falte verkörpert die Idee einer rekursiven Funktion. Zum Beispiel, wenn wir wollten eine Liste von Zahlen rekursiv fassen wir es als definieren könnte:

from operator import add # this is just '+' as a function 
def sum(xs): 
    return foldl(add, 0, xs) 

Wenn wir eine richtige Falte zu definieren, waren wie folgt:

def foldr(f,acc,xs): 
    if not xs:   
    return acc 
    head, *tail = xs 
    return f(head, foldr(f, acc, tail)) 

Dann ruft die foldr(cons, [], xs) zurückkehren eine Liste identisch mit der ursprünglichen.