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

Question

问题：通过掷骰子一次或多次来计算构造sumn的方法数。每次投掷产生的结果介于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

我见过在web上编写阶乘函数作为尾部递归的例子，但这很容易。无法应用累加器技巧将所需答案存储为函数调用中的附加参数。一般来说，还有其他的技巧有效吗

这也可以重写为迭代函数，但我正在寻找将递归函数转换为尾部递归函数的一般方法。给定的问题、代码和Python只是一个示例。没有什么特别的

Answer 1

这是一个简单的解决方案，无递归，无任何，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的卷数

Answer 2

解决堆栈溢出问题的一种方法是手动模拟调用堆栈

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