¿Cómo puedo revertir una lista usando la recursividad en Python?

Question

Quiero tener una función que devuelva el reverso de una lista que se proporciona, usando la recursión. ¿Cómo puedo hacer eso?

Answer 1

Agregue el primer elemento de la lista a una sublista invertida:

mylist = [1, 2, 3, 4, 5]
backwards = lambda l: (backwards (l[1:]) + l[:1] if l else []) 
print backwards (mylist)

Answer 2

Un poco más explícito:

def rev(l):
    if len(l) == 0: return []
    return [l[-1]] + rev(l[:-1])

---

Esto se convierte en:

def rev(l):
    if not l: return []
    return [l[-1]] + rev(l[:-1])

Que se convierte en:

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

Lo que es lo mismo que otra respuesta.

---

Estilo recursivo / CPS de cola (para el que Python no se optimiza):

def rev(l, k):
    if len(l) == 0: return k([])
    def b(res):
        return k([l[-1]] + res)
    return rev(l[:-1],b)


>>> rev([1, 2, 3, 4, 5], lambda x: x)
[5, 4, 3, 2, 1]

Answer 3

Sé que no es una respuesta útil (aunque esta pregunta ya ha sido respondida), pero en cualquier código real, no hagas eso. Python no puede optimizar las llamadas de cola, tiene llamadas de función lentas y tiene una profundidad de recursión fija, por lo que hay al menos 3 razones por las que hacerlo en forma iterativa.

Answer 4

El truco es unirse a después de recurrente:

def backwards(l):
  if not l:
    return
  x, y = l[0], l[1:]
  return backwards(y) + [x]

Answer 5

def revList(alist):
    if len(alist) == 1:       
        return alist #base case
    else:
        return revList(alist[1:]) + [alist[0]]

print revList([1,2,3,4])
#prints [4,3,2,1]

Answer 6

Usa la división & amp; conquistar la estrategia. Los algoritmos D & amp; C son algoritmos recursivos. Para resolver este problema utilizando D & amp; C, hay dos pasos:

1. Averiguar el caso base. Este debería ser el caso más simple posible.
2. Divida o disminuya su problema hasta que se convierta en el caso base.

Paso 1: averiguar el caso base. ¿Cuál es la lista más simple que podrías ¿obtener? Si obtiene una lista con 0 o 1 elemento, es bastante fácil de resumir.

if len(l) == 0:  #base case
    return []

Paso 2: necesitas acercarte a una lista vacía con cada recursivo llamar

recursive(l)    #recursion case

por ejemplo

l = [1,2,4,6]
def recursive(l):
    if len(l) == 0:
        return []  # base case
    else:
        return [l.pop()] + recursive(l)  # recusrive case


print recursive(l)

>[6,4,2,1]

Fuente: Grokking Algorithms

Answer 7

Este se invierte en su lugar. (Por supuesto, una versión iterativa sería mejor, pero tiene que ser recursiva, ¿no es así?)

def reverse(l, first=0, last=-1):
    if first >= len(l)/2: return
    l[first], l[last] = l[last], l[first]
    reverse(l, first+1, last-1)

mylist = [1,2,3,4,5]
print mylist
reverse(mylist)
print mylist

Answer 8

def reverse(q):
    if len(q) != 0:
        temp = q.pop(0)
        reverse(q)
        q.append(temp)
    return q

Answer 9

parece más simple:

    def reverse (n):
        if not n: return []
        return [n.pop()]+reverse(n)

Answer 10

Toma el primer elemento, invierte el resto de la lista de forma recursiva y agrega el primer elemento al final de la lista.

Answer 11

def reverseList(listName,newList = None):
if newList == None:
    newList = []
if len(listName)>0:
    newList.append((listName.pop()))
    return reverseList(listName, newList)
else:
    return newList

imprimir la lista inversa ([1,2,3,4]) [4,3,2,1]

Answer 12

Usando el argumento y la recursión predeterminados de Mutable:

def hello(x,d=[]):
    d.append(x[-1])
    if len(x)<=1:
        s="".join(d)
        print(s)

    else:
        return hello(x[:-1])

hello("word")

información adicional

x[-1]    # last item in the array
x[-2:]   # last two items in the array
x[:-2]   # everything except the last two items

La parte de recursión es hello (x [: - 1]) , donde su llamada hello vuelve a funcionar después de x [: - 1]

Answer 13

¿Por qué no?

a = [1,2,3,4,5]
a = [a[i] for i in xrange(len(a)-1, -1, -1)] # now a is reversed!

Answer 14

¡Esto también revertirá las listas anidadas!

A = [1, 2, [31, 32], 4, [51, [521, [12, 25, [4, 78, 45], 456, [444, 111]],522], 53], 6]

def reverseList(L):

    # Empty list
    if len(L) == 0:
        return

    # List with one element
    if len(L) == 1:

        # Check if that's a list
        if isinstance(L[0], list):
            return [reverseList(L[0])]
        else:
            return L

    # List has more elements
    else:
        # Get the reversed version of first list as well as the first element
        return reverseList(L[1:]) + reverseList(L[:1])

print A
print reverseList(A)

BLOG de Padmal