Python-将递归转换为尾递归

Question

找出从网格的一个角到对角的方法数，仅向下或向右。我初步想到用递归来解决问题:

def find_num_of_ways(x: int, y: int):
    if x == 0 or y == 0:
        return 1
    return find_num_of_ways(x - 1, y) + find_num_of_ways(x, y - 1)

当 x 和 y 增加时，这可能是堆栈溢出。想要找到更好的方法来重构这一点，一种是转换为尾递归。但是给定签名中的2个变量，那么如何累加结果以使其成为尾递归呢？

Answer 1

我对此的分析是，计算答案需要很长时间，以至于你会在堆栈溢出之前就走开。我建议我们完全删除递归，并将其作为盒子和球的组合问题来完成

(x + y - 1)!
------------
 y!(x - 1)!

加上相反的内容:

(y + x - 1)!
------------
 x!(y - 1)!

也就是说，Python 方面:

from math import factorial as f

def find_num_of_ways(x, y):
    return f(x + y - 1) // (f(y) * f(x - 1)) + f(y + x - 1) // (f(x) * f(y - 1)) 

print(find_num_of_ways(10, 10))

输出

> python3 test.py
184756
>

从性能角度来看，参数:

find_num_of_waysTail(13, 14)

在我的机器上，OP的原始递归解决方案需要9秒，@Mike67的计数器解决方案需要大约12秒，而我上面的解决方案大约需要0.05秒。全部产生结果 20058300。