最长Collat​​z序列 - 记忆 - Python-迭代与递归

Question

dict={} 
def recur(n): 
    counter=1 
    original=n 
    while n!=1: 
     n = n/2 if n % 2 == 0 else 3*n+1 
     if n in dict: 
      counter=counter+dict[n] 
      dict[original]=counter 
      return counter 

     counter=counter+1 
    dict[original]=counter 
    return counter 
for i in range(1,1000000): 
    recur(i) 
print(max(dict.keys(), key=(lambda k: dict[k]))) 

如何记忆一次调用中使用的所有数字？例如，当我调用recur（13）时，它将只在字典中存储13的值，但不存储用于重复（13）中的40,20,10,5等的值（012）

另外，我无法产生递归函数，因为我可以计数（通过在函数中添加计数器参数），但是我不能在字典中添加值。

请建议一种方式，以便尽可能多的值存储在内存中，而且函数是递归的？

Answer 1

这是编写我能想到的递归函数的最易读（也是相当pythonic）的方式;它基本上只是阐明了规则建立的顺序，你会解释给别人：

count = {} 

def recur(n): 
    if n not in count: # memoize 
     if n == 1: 
      count[n] = 0 # finished 
     else: 
      count[n] = recur(n//2 if n % 2 == 0 else 3*n + 1) 
     count[n] += 1 # this step 
    return count[n] 

for i in range(1, 100): 
    recur(i) 

for item in sorted(count.items()): 
    print(item) 

正开始在count缓存，1将允许这样的优化，但牺牲形成规则的直接翻译成代码：

count = {1: 1} 

def recur(n): 
    if n not in count: # memoize 
     count[n] = 1 + recur(n//2 if n % 2 == 0 else 3*n + 1) 
    return count[n]