從迭代遞歸 - 重新排序列表

我有一個列表：從迭代遞歸 - 重新排序列表

L = [0,'a','b','c']

如果我運行以下命令：

sortedList = [] 
while len(L) > 0: 
    item = L.pop() 
    sortedList.append(item) 
print(sortedList)

輸出：

['c', 'b', 'a', 0]

舉一個簡單的演習試圖理解遞歸我想把上面的遞歸函數。我有兩次嘗試 - 我該如何修復一個或兩個 - 或者是否存在遞歸解決方案？

def extract(Seq): 
    if Seq == [0]: 
     return s.append(0) 
    else: 
     extract(Seq[:len(Seq)-1]) 

     if not s: s = [] 
     x=Seq.pop() 
     return s.append(x) 

M = [0,'a','b','c'] 
print(extract(M))

def extract2(Seq): 
    s=[] 
    if Seq: 
     return s.append(Seq.pop()) 
     extract2(Seq) 

N = [0,'a','b','c'] 
print(extract(N))

來源

2014-01-29 whytheq

首先，避免使用大寫首字母爲變量，甚至更多的時候變量都有一個名字，可以看起來像一個類，這很混亂。 – zmo

用這個着名的遞歸排序算法找到一些靈感：http://en.wikipedia.org/wiki/Quicksort –

你在這裏得到了幾個很好的答案，儘管幫你實際做到了這一點，這裏有一點小技巧：當你創建一個遞歸算法時，你通常需要考慮三個步驟：初始化遞歸;檢查遞歸條件的結束;做遞歸。在代碼中不一定是明確的，不一定按照這個順序，但是你需要考慮這些。 – zmo

遞歸的解決辦法是：

def extract3(seq): 
    if not seq: 
     return seq 
    return [seq.pop()] + extract3(seq)

但是這個修改你想要的東西可能不是輸入列表中。因此，最好根據需要進行切片輸入列表：

def extract4(seq): 
    if not seq: 
     return seq 
    return [seq[-1]] + extract4(seq[:-1])

其中seq[-1]的意思是「取seq最後一個元素」和seq[:-1]意思是「採取的seq所有元素除了最後一個」。函數extract4通過根據需要獲取元素並且不修改給定序列seq來建立新列表。

您也可以使用這將與extract5(N, [])被稱爲蓄電池：

def extract5(seq, acc): 
    if not seq: 
     return acc 
    acc.append(seq[-1]) 
    return extract5(seq[:-1], acc)

來源

2014-01-29 14:04:52

+1謝謝西蒙。我在OP中有一個額外的列表's'的想法永遠不會在遞歸解決方案中工作？或者是否可以包含一個額外的列表？ – whytheq

@whytheq：我不確定你需要變量's'的位置。您可以包含一個額外的列表（稱爲累加器），以使遞歸更高效。但對於基本的遞歸解決方案，不需要額外的列表或變量。 –

感謝西蒙 - 出於興趣如何提取累加器外觀 - 這是一個很容易的補充：在我的他們只是不斷重寫覆蓋，因此我不確定累積器的代碼位於 – whytheq

從迭代遞歸 - 重新排序列表

回答

相關問題