Comment inverser une liste à l'aide de la récursivité en Python?

StackOverflow https://stackoverflow.com/questions/216119

  •  03-07-2019
  •  | 
  •  

Question

Je souhaite avoir une fonction qui renverra l'inverse d'une liste qui lui est donnée - en utilisant la récursivité. Comment puis-je faire cela?

Était-ce utile?

La solution

Ajoutez le premier élément de la liste à une sous-liste inversée: 

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

Autres conseils

Un peu plus explicite: 

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

Cela se transforme en: 

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

Qui se transforme en: 

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

Qui est identique à une autre réponse.

Style récursif de queue / CPS (ce que python n'optimise pas de toute façon): 

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]

Je sais que ce n'est pas une réponse utile (même si cette question a déjà été posée), mais dans tout code réel, veuillez ne pas le faire. Python ne peut pas optimiser les appels en aval, a des appels de fonction lents et une profondeur de récursivité fixe. Il y a donc au moins trois raisons pour lesquelles le faire de manière itérative à la place.

L'astuce consiste à rejoindre après récursif: 

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

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]

Utilisez le menu Divide & amp; stratégie de conquête. Les algorithmes D & C sont des algorithmes récursifs. Pour résoudre ce problème avec D & C, vous devez suivre deux étapes:

  1. Déterminez le cas de base. Cela devrait être le cas le plus simple possible.
  2. Divisez ou diminuez votre problème jusqu'à ce qu'il devienne le cas de base.

Étape 1: Déterminez le cas de base. Quelle est la liste la plus simple que vous puissiez obtenir? Si vous obtenez une liste avec 0 ou 1 élément, c'est assez facile à résumer. 

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

Étape 2: Vous devez vous rapprocher d’une liste vide avec chaque récursif appeler 

recursive(l)    #recursion case

par exemple 

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]

Source: Algorithmes de Grokking

Celui-ci s'inverse en place. (Bien sûr, une version itérative serait préférable, mais elle doit être récursive, n'est-ce pas?) 

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

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

semble plus simple: 

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

Prenez le premier élément, inversez le reste de la liste de manière récursive et ajoutez le premier élément à la fin de la liste. 

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

print reverseList ([1,2,3,4]) [4,3,2,1]

Utilisation de l'argument et de la récursion par défaut mutables: 

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

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

hello("word")

informations supplémentaires 

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

La partie récursive est hello (x [: - 1]) où sa fonction hello d’appel fonctionne à nouveau après x [: - 1]

Pourquoi pas: 

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

Ceci inversera également une liste imbriquée! 

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

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top