如何实现对应2的幂的递归函数及现有代码校验与修改

递归判定 #

你编写的代码属于递归函数，因为函数fun的内部逻辑中调用了自身，满足递归函数的基本定义。但代码逻辑存在错误，既不符合你给出的参考算法，也无法正常运行得到正确的2的幂结果。

现有代码的问题 #

• 参考算法的else分支要求累加fun(1)到fun(n-1)的结果，但你代码中range(n)生成的是0到n-1的整数，会调用未定义边界逻辑的fun(0)，运行时会触发无限递归最终栈溢出。
• 变量缩进不符合Python语法要求，原样运行会直接报语法错误。

修正方案 #

方案1：对齐参考算法实现 #

调整循环范围，加上正确缩进即可：

def fun(n):
    if n == 1 or n == 2:
        return 1
    sum_val = 0
    # 从1遍历到n-1，对齐参考算法的累加范围
    for i in range(1, n):
        sum_val += fun(i)
    return sum_val

方案2：无循环的纯递归实现 #

我们可以通过递推公式简化逻辑：

已知fun(n) = fun(1) + fun(2) + ... + fun(n-1)
可得fun(n-1) = fun(1) + fun(2) + ... + fun(n-2)
两式相减得fun(n) = 2 * fun(n-1)
基于这个规律可以写出完全不需要循环的递归实现，运行效率更高：

def fun(n):
    # 边界条件
    if n == 1 or n == 2:
        return 1
    # 递归关系
    return 2 * fun(n-1)

效果验证 #

两种修正后的代码计算结果一致：

• fun(1) = 1、fun(2) = 1
• fun(3) = 2、fun(4) = 4、fun(5) = 8、fun(6) = 16
  完全符合计算2的幂的需求。

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