python - 将递归函数转换为迭代函数

Question

虽然这看起来像是重复的(也许是，但我还没有找到解决此版本问题的方法)，但我认为不是。

下面是我的递归函数，它打破了 python 的递归限制，我需要让它迭代，但我遇到了一些问题，看看它是如何实现的。

def countChain(n, cache):
    if cache[n] != -1:
        return cache[n]

    if n % 2 == 0:
        cache[n] = 1 + countChain(n / 2, cache)
    else:
        cache[n] = 2 + countChain((3 * n + 1) / 2, cache)

    return cache[n]

请注意，这里我的缓存列表中有 100 万个元素...(这就是递归杀死 python 的原因)。我见过人们使用累加器来完成这项工作，但在这里我没有直接返回递归调用的结果，这使得这个想法难以实现。

编辑

第一个递归调用应该是 cache[n] = 1 + countChain(n/2, cache) 而不是 cache[n] = 1 + countChain(n, cache)

编辑 2

有人要求提供示例数据，所以我将简单地输入整个代码(不是那么长)以便更好地理解。

import time
import sys
import math

def main():
    target = int(sys.argv[1])

    start = time.time()
    longest = 0
    answer = -1

    for i in range(int(target/2), target):
        if countChain(i) > longest:
            longest = countChain(i)
            answer = i

    print("Result = ", answer, " in ", (time.time() - start), " seconds")

def countChain(n,cache={1:0}):
    if n not in cache: 
        if n % 2 == 0:
            cache[n] = 1 + countChain(n//2, cache)
        else:
            cache[n] = 2 + countChain((3 * n + 1) // 2, cache)
    return cache[n]

if __name__ == "__main__":
    main()

通常输入1000000

另外 else 应该是 2 + ...

Answer 1

您始终可以使用堆栈将递归函数转换为迭代函数。以下是我的做法:

def countChain(n):
    cache = { 1: 0 }
    stack = [n]
    while n not in cache:
      n_curr = stack.pop()

      if n_curr % 2 == 0:
        if n_curr / 2 in cache:
          cache[n_curr] = 1 + cache[n_curr / 2]
        else:
          stack.append(n_curr)
          stack.append(n_curr / 2)
      else:
        if (3 * n_curr + 1) / 2 in cache:
          cache[n_curr] = 3 + cache[(3 * n_curr + 1) / 2]
        else:
          stack.append(n_curr)
          stack.append((3 * n_curr + 1) / 2)

    return cache[n]