Inversione di un elenco utilizzando la ricorsione in python

Question

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

Sono arrivato fino a qui ma non so cosa fare dopo. Pratico la ricorsione per i miei esami. Se qualcuno potesse aiutarmi, sarei grato.

Answer 1

Il caso base è che non si dispone di un elenco, quindi si desidera restituire l'elenco vuoto.

Caso ricorsivo è quello che si fa, quindi si desidera anteporre l'ultimo elemento alla chiamata ricorsiva sul resto dell'elenco.

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) 

Ecco un pilota che ho scritto:

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

Questo restituito:

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

Questo funziona con tutti i iterabili.

Answer 2

Pensa a ciò che stai cercando di ottenere per ogni chiamata ricorsiva. Il legame che thefourtheye menzioni nel suo commento mostra davvero un buon esempio di come si somma una lista con ricorsione:

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

Usando questo come un punto base, come è possibile quindi ottenere una lista invertita? Sarebbe probabilmente simile a:

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

Questo quindi mostra in modo più conciso ciò che si desidera ottenere. Alla fine, questo è ciò che otterresti.

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

Answer 3

vostro caso semplice va bene, se la lunghezza della lista è 1 (o più piccolo), è sufficiente tornare alla lista. In effetti, possiamo semplicemente verificare se l'elenco è vuoto (emettendo if not lst). Se la lista è più grande, devi pensare a come semplificare il problema nel caso ricorsivo. In parole, puoi formularlo in questo modo: Se l'elenco è più lungo di 1, dammi l'ultimo elemento di quell'elenco esteso dalla lista che ottengo quando inverto l'elenco dato senza l'ultimo elemento in esso. Quest'ultima lista è una più piccola della lista originale, quindi il problema è semplificato.

in codice:

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

un altro modo

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

Answer 5

una versione scritta con l'idea di un fold

Abbiamo bisogno di una funzione che chiameremo cons (questo deriva da lisp/schema ecc.). Prende un elemento e una lista e aggiunge quell'elemento alla testa (inizio) della lista. Si noti che in Python questo non è efficiente.

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

Ora la funzione piega (in senso stretto una piega a sinistra). Questa è una funzione a sé stante e può essere utilizzata per molte cose (vedi il link) l'equivalente python sarebbe probabilmente reduce.Si noti che ci vuole una funzione f e si applica questa funzione per la testa della lista e la variabile acc (abbreviazione di accumulatore)

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

Ora possiamo scrivere una versione di inversione che è ricorsiva (perché piega è ricorsiva)

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

Quindi una piega racchiude l'idea di una funzione ricorsiva. Per esempio, se volessimo riassumere in modo ricorsivo una lista di numeri che potremmo definire come:

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

Se dovessimo definire un diritto piega, come segue:

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

quindi chiamando il foldr(cons, [], xs) tornerà una lista identica a quella iniziale.