如何限制python中的遞歸深度？

Question

我有一個元素列表。我想知道列表中是否有兩對元素，其中元素對的元素具有相同的值。

我的想法是，我首先比較列表中的所有元素，如果找到一對，則從列表中刪除該對，然後再繼續。因此我認爲我可以使用遞歸來完成這個任務，但是將深度限制爲2來解決問題。

這是我第一次嘗試：

recursion_depth=0 
     def is_twopair(card): 
      nonlocal recursion_depth 
      if recursion_depth==2: return True 
      for i in range(0, len(card)): 
       for k in range(i+1,len(card)): 
        if card[i].value==card[k].value: 
         del card[k], card[i] 
         recursion_depth+=1 
         is_twopair(card)  
        else: continue 
       else: continue 
      else: return False 

我使用變量recursion_depth記錄遞歸的深度，但後來意識到，返回的命令不會立即終止函數並返回true，但回報而不是原來的調用者is_twopair（卡）。所以我的問題是：

1. 有沒有辦法立即終止函數並返回結果true？
2. 有沒有辦法限制遞歸的深度？

我知道可能有幾種方法來解決這個問題。但我想保持忠實於我的想法，並將其作爲學習的機會。

Answer 1

我認爲你缺少一塊是return調用一個遞歸調用的結果傳回了以前的來電者：

if card[i].value==card[k].value: 
    del card[k], card[i] 
    recursion_depth+=1 
    return is_twopair(card)  # add return here! 

我真的不認爲遞歸是一種自然的方式要解決這個問題，但是隨着上述變化，它應該起作用。您可以通過將depth作爲可選參數來避免需要使用nonlocal變量。

Answer 2

yourList = [1,1,2,2,3,4] 
yourDict = {} 
for i in yourList: 
    yourDict[i] = yourList.count(i) 

此代碼將返回列表中ocurrences的數量爲每一個值，因此您可以確定的對數..

在這種情況下：

yourDict - - > { 1：2,2：2,3：1,4：1}

值1出現2次，值2出現2次，值3和4出現1次。

Answer 3

我不相信你可以在沒有一些嚴重的黑魔法的情況下「突破」遞歸，也不相信你應該嘗試。將返回值級聯到調用鏈上通常是一種很好的方法。

我個人避免使用非局部變量並在每個函數調用的範圍內跟蹤遞歸深度。

def remove_pairs(card, count=2, depth=0): 
    if depth == count: 
     return card 

    for i in range(0, len(card)): 
     for j in range(i+1, len(card)): 
      if card[i].value == card[j].value: 
       del card[j], card[i] 
       return remove_pairs(card, count, depth+1) # add return here 

將深度的跟蹤移動到函數本身將允許從不同位置重複調用該函數而不會出現問題。

此外，代碼可以使用itertools.combinations清理一些。

from itertools import combinations 

def remove_pairs(cards, count=2, depth=0): 
    if depth == count: 
     return cards 

    for card1, card2 in combinations(cards, 2): 
     if card1.value == card2.value: 
      cards.remove(card1) 
      cards.remove(card2) 
      return remove_pairs(cards, count, depth+1)