如何计算指定Python递归函数中的减法运算总次数

首先明确该递归函数的减法触发规则：每次调用f(k)且k≥3时，return语句需要计算k-1、k-2、k-3三个值，对应3次减法运算；k小于3时直接返回1，没有减法产生。

递推公式 #

我们定义C(k)为调用f(k)过程中产生的减法总次数，可以得到如下计算规则：

• 边界条件：C(0) = C(1) = C(2) = 0（k小于3时无减法）
• 递推关系（k≥3）：C(k) = 3 + C(k-1) + C(k-2) + C(k-3)（当前调用产生3次减法，再加三个子调用的减法总和）

小值验证 #

我们可以用小数值代入验证结果正确性：

• k=3：C(3)=3+0+0+0=3，实际执行时仅f(3)自身触发3次减法，结果正确
• k=4：C(4)=3 + C(3)+C(2)+C(1)=3+3=6
• k=5：C(5)=3 + C(4)+C(3)+C(2)=3+6+3=12

高效计算实现 #

如果要计算大k值的结果，推荐用迭代方式避免递归重复计算，参考代码如下：

def calc_sub_count(k):
    if k < 3:
        return 0
    # 初始化前三个值对应C(0), C(1), C(2)
    c0, c1, c2 = 0, 0, 0
    for i in range(3, k+1):
        cur = 3 + c0 + c1 + c2
        c0, c1, c2 = c1, c2, cur
    return c2

内容的提问来源于stack exchange，提问作者Sander