将递归函数改写为尾部递归函数

Question

问题：数一数构造和的方法有多少种？n 通过投掷一个或多个骰子。每次投掷的结果在1到6之间。

解决办法。我为它写了一个递归的解决方案，它可以输出正确的答案。对于大的 n 它应该会遇到堆栈溢出。所以我想避免这种情况，用尾部递归的方法重写代码。这是我的代码。

def numWays(n, arr):
  answer = 0
  for item in arr:
    if item <= n:
      if n == item:
        answer += 1
      else:
        answer += numWays(n-item, arr)

  return answer

li = [i for i in range(1,7)]
print(numWays(5, li)) #example n=5

我在网上看到过把阶乘函数写成尾部递归的例子 但那很容易。但我无法应用累加器技巧将所需的答案存储为函数调用中的额外参数。有没有其他的技巧，一般情况下是可行的？

这也可以重写成迭代函数，但我正在寻找一般的方法来将递归函数转换为尾部递归。给出的问题、代码和Python只是为了举例。没有具体的那些。

Answer 1

有一个方法可以让你绕过堆栈溢出的问题，那就是手动模拟调用栈。

def numWays(n, arr):
    call_stack = [(n, arr)]
    answer = 0
    while call_stack:
        n, arr = call_stack.pop(0)
        for item in arr:
            if item <= n:
                if n == item:
                    answer += 1
                else:
                    call_stack.insert(0, (n-item, arr))
    return answer


li = [i for i in range(1, 7)]
print(numWays(5, li))

输出。

16

Answer 2

这是一个简单的解决方案，没有递归，没有什么，O(N):

#!/usr/bin/env python

DICE = 6    # how many sides our dice has

rolls = [1]
for i in range(1,800) :
    rolls.append(sum(rolls[-min(i,DICE):]))

print rolls[:16]  # print results for the first 16 (zero-based!!)
print rolls[610]  # print result for 610 steps

结果：

[1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109]
14527490260516100855695859704819627818108010882741117227956927412305738742399171256642436462028811566617818991926058940988565927870172608545709804976244851391054850231415387973537361

很容易计算出N=50000或500000的卷数