Как ограничить глубину рекурсии в 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 записать глубину рекурсии, но потом понимает, что команда возврата не сразу прекращает функцию и возвращает истину, но возвращается вместо этого его первоначальный вызывающий 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! 

Я не думаю, что рекурсия является естественным способом для решения этой проблемы, но с вышеуказанным изменением она должна работать. Вы можете избежать необходимости использовать переменную nonlocal, передав depth в качестве необязательного параметра.

Answer 2

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

Этот код будет возвращать количество вхождений для каждого значения в списке, так что вы можете детерминированное количество пара ..

В этом случае:

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)