Как я могу перевернуть список с помощью рекурсии в Python?

Question

Я хочу иметь функцию, которая будет возвращать обратный список, который ему дан - используя рекурсию. Как я могу это сделать?

Answer 1

Добавить первый элемент списка в обратный подсписок:

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

Answer 2

Чуть более явно:

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

---

Это превращается в:

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

Что превращается в:

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

Что совпадает с другим ответом.

---

Хвост рекурсивный / стиль CPS (который Python в любом случае не оптимизирует):

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

Я знаю, что это не полезный ответ (хотя на этот вопрос уже был дан ответ), но в любом реальном коде, пожалуйста, не делайте этого. Python не может оптимизировать хвостовые вызовы, имеет медленные вызовы функций и имеет фиксированную глубину рекурсии, поэтому есть как минимум 3 причины, по которым делать это итеративно.

Answer 4

Хитрость заключается в том, чтобы присоединиться к после повторения:

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

Answer 5

Используйте стратегию «Разделяй и властвуй». Алгоритмы D & C являются рекурсивными алгоритмами. Чтобы решить эту проблему с помощью D & C, есть два шага:

1. Выясните базовый случай. Это должен быть простейший случай.
2. Разделите или уменьшите вашу проблему, пока она не станет базовым вариантом.

Шаг 1: Определите базовый вариант. Какой самый простой список вы могли бы получить? Если вы получите список с 0 или 1 элементом, это довольно просто подвести итог.

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

Шаг 2: вам нужно перемещаться ближе к пустому списку с каждым рекурсивным звоните

recursive(l)    #recursion case

например

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]

Источник: Алгоритмы Гроккинга

Answer 6

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 7

выглядит проще:

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

Answer 8

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

Answer 9

Этот переворачивается на месте. (Конечно, итеративная версия была бы лучше, но она должна быть рекурсивной, не так ли?)

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 10

Это также обратит вложенные списки!

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)

БЛОГ Падмаля