如何限制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)