递归函数到迭代函数的转换

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]

注意这里我的缓存列表有一百万个元素。。。（这就是递归杀死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_recursive_cache(n):
    if n not in cache: 
        if n % 2 == 0:
            cache[n] = 1 + countchain_recursif(n//2)
        else:
            cache[n] = 1 + countchain_recursif(3 * n + 1)
    return cache[n]

纯粹的迭代法：

def countchain_iterative(n):
    count=0
    while n>1:
        if n%2 == 0 : 
            n //= 2
            count += 1
        else :
            n = (3*n+1)//2
            count += 2
    return count

以及无堆栈缓存版本：

def countchain_iterative_cache(n):
    count = 0
    n0=n
    while n not in cache:
            count += 1
            if n%2 == 0 : n //= 2
            else : n = 3*n+1
    count+= cache[n]
    n=n0
    while n not in cache:
            cache[n]=count
            count-=1
            if n%2 == 0 : n //= 2
            else : n = 3*n+1
    return cache[n]

如果缓存在函数中，则缓存机制不感兴趣。一定是的 全球将加快进一步的呼吁。你知道吗

时间安排如下：

%time  for i in range(1,10**4) : countchain_iterative(i)
cache={1:0}
%time  for i in range(1,10**4) : countchain_iterative_cache(i)
cache={1:0}
%time  for i in range(1,10**4) : countchain_recursive_cache(i)
%time  for i in range(1,10**4) : countChain_morcedist(i)

# respectively :
Wall time: 490 ms
Wall time: 80 ms
Wall time: 54 ms
Wall time: 3.82 s

但是如果你只想要一个计数链，最有效的方法是无缓存迭代法：

%time countchain_iterative(10**10_000)  
Wall time: 6.37 s
Out[381]: 177856

最后，我猜想你永远不会在迭代构造中破坏快速递归函数：

%time for i in range(1,10**7): countchain_recursif(i)
Wall time: 1min 8s

Answer 2

通过使用堆栈，您始终可以将递归函数转换为迭代函数。我会这样做：

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]