Recaman с рекурсией

Question

lst = []
def recaman(n):
  #print lst
  if n == 1:
    lst.append(n)
    return 1
  else:
    a = recaman(n-1)
    am = a - n
    ap = a + n
    if am > 0 and am not in lst:
      lst.append(am)
      return am
    else:
      lst.append(ap)
      return ap
  #print lst
  #lst.append(temp)   
#print recaman(1)
#print recaman(2)
#print recaman(3)
#print recaman(4)
#print recaman(5)
print recaman(6)
#13

Это может быть простой вопрос для вас, но я не смог найти объяснение этого: если я печатаю только recaman(6) Вывод будет 13, что верно, однако, если я печатаю recaman(5) и recaman(6) в то же время, вывод равен 7 and 11, который должен был быть 7 and 13. Почему это?

Answer 1

Проблема в том, что список определяется глобально, поэтому после вызова recaman следующий вызов функции дает неожиданные результаты, поскольку в списке все еще есть элементы:

print(recaman(5)) # 7
print(lst) # [1, 3, 6, 2, 7]

Решение

Существует много возможных решений, но простое, на мой взгляд, элегантное - заставить функцию recaman принимать список в качестве параметра. Этот список затем может быть передан в рекурсивных вызовах. Изначально вы бы назвали это пустым списком. Таким образом, окончательный код становится:

def recaman(n, lst):
  if n == 1:
    lst.append(n)
    return 1
  else:
    a = recaman(n-1, lst)
    am = a - n
    ap = a + n
    if am > 0 and am not in lst:
      lst.append(am)
      return am
    else:
      lst.append(ap)
      return ap

print(recaman(5, [])) # 7
print(recaman(6, [])) # 13