resueltos - ¿Cómo invierto una lista usando la recursión en Python?

ejercicios resueltos de recursividad en python

Question

Quiero tener una función que devolverá el reverso de una lista que se le da, utilizando recursividad. ¿Cómo puedo hacer eso?

Answer 1

¡Esto invertirá una lista anidada también!

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

Answer 2

Añada 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 3

El truco es unirse después de la recursión:

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

Answer 4

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

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 5

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 6

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 para hacerlo iterativamente.

Answer 7

Tome el primer elemento, invierta el resto de la lista recursivamente y agregue el primer elemento al final de la lista.

Answer 8

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 cual es lo mismo que otra respuesta.

Cola recursiva / estilo CPS (que python no optimiza de todos modos):

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 9

Usa la estrategia Dividir y vencer. Los algoritmos de D & C son algoritmos recursivos. Para resolver este problema usando D & C, hay dos pasos:

1. Calcule 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: averigua el caso base. ¿Cuál es la lista más simple que podrías obtener? Si obtienes una lista con 0 o 1 elemento, es bastante fácil de resumir.

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

Paso 2: debe acercarse a una lista vacía con cada llamada recursiva

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: Algoritmos de Grokking

Answer 10

Usando el argumento y la recursión por defecto 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 recursiva es hello(x[:-1]) donde su función hola vuelve a funcionar después de x[:-1]

Answer 11

parece más simple:

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

Answer 12

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 13

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

Answer 14

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 reverseList ([1,2,3,4]) [4,3,2,1]