最长的 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 的值，而不存储在 recur(13)

中使用的 40、20、10、5 等值

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

请提出一种方法，使最大可能值存储在内存中，并且该函数是递归的？

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)

用 1 初始化 count 缓存将允许优化，但会牺牲将形成规则直接转换为代码的过程：

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]