将递归函数重写为尾递归函数 [英] Rewrite the recursive function into tail recursive function

问题描述

问题:计数一次或多次掷骰子来构造总和 n 的方法的数量.每次掷出的结果在1到6之间.

Problem: Count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.

解决方案:我已经为其编写了一个递归解决方案，该解决方案可以输出正确的答案.对于 n 的较大值，它应该达到堆栈溢出.因此，我想避免这种情况，并使用尾部递归方法重写代码.这是我的代码:

Solution: I have written a recursive solution for it which outputs correct answer. For large values of n it should hit stack overflow. So I want to avoid it and rewrite the code using tail recursive approach. Here's my code:

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

我已经看到了将阶乘函数编写为网络上的尾递归的示例，但这很容易.无法应用该累加器技巧来将所需答案存储为函数调用中的附加参数.一般还有其他技巧吗?

I've seen example of writing factorial function as tail recursive on web but that was easy. Not able to apply that accumulator trick to store the required answer as an additional argument in the function call. Are there any other tricks which work in general?

这也可以重写为迭代函数，但是我正在寻找将递归函数转换为尾递归的方法.给定的问题，代码和Python仅作为示例.没什么特别的.

This could be rewritten as iterative function also but I am looking for ways in general to convert recursive functions to tail-recursive. The given problem, code, and Python is just for an example. Nothing specific about those.

推荐答案

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

One way for you to get around the stack overflow problem would be to simulate the callstack manually.

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

这篇关于将递归函数重写为尾递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！