python - 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和13的7和11。这是为什么？

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