كيف يمكنني عكس قائمة باستخدام العودية في بايثون؟

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 (التي الثعبان لا تحسين لأي حال):

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

وأنا أعلم أنها ليست إجابة مفيدة (وإن كان هذا السؤال أجاب بالفعل)، ولكن في أي رمز حقيقي، من فضلك لا تفعل ذلك. الثعبان لا يمكن تحسين ذيل المكالمات والمكالمات وظيفة لديها بطيئة ولها عمق العودية ثابتة، لذلك هناك 3 أسباب على الأقل للقيام بذلك بشكل متكرر بدلا من ذلك.

Answer 4

وهو خدعة للانضمام <م> بعد recursing:

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

استخدم استراتيجية فرق تسد.خوارزميات 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 7

وهذا واحد يعكس في المكان. (وبطبيعة الحال فإن وجود نسخة تكرارية يكون أفضل، ولكن يجب أن يكون العودية، لم ذلك؟)

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

ويبدو أكثر بساطة:

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

Answer 10

ويأخذ العنصر الأول، عكس بقية القائمة بشكل متكرر، وإلحاق العنصر الأول في نهاية القائمة.

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

والطباعة reverseList ([1،2،3،4]) [4،3،2،1]

Answer 12

<ع> استخدام الوسيطة الافتراضية قابلة للتغيير والعودية:

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

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

hello("word")

مزيد من المعلومات

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

ووhello(x[:-1]) العودية الجزء حيث تدعو مرحبا ظيفتها مرة أخرى بعد x[:-1]

Answer 13

لماذا لا:

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

Answer 14

وهذا سوف عكس القوائم المتداخلة أيضا!

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)

Padmal في BLOG