python - 如何将 2**n - 1 写为递归函数？

Question

我需要一个接受 n 并返回 2ⁿ - 1 的函数。听起来很简单，但该函数必须是递归的。到目前为止我只有 2ⁿ:

def required_steps(n):
    if n == 0:
        return 1
    return 2 * req_steps(n-1)

练习指出:“您可以假设参数 n 始终是一个大于 0 的正整数”

Answer 1

2**n -1 也可以是 1+2+4+...+2^n-1单个递归函数(没有第二个函数从 2 的幂中减去 1)。

提示:1+2*(1+2*(...))

解决方案如下，想先尝试一下提示的就不要看。

<小时/>

如果 n 保证大于零(正如问题陈述中实际 promise 的那样)，则此方法有效:

def required_steps(n):
    if n == 1: # changed because we need one less going down
        return 1
    return 1 + 2 * required_steps(n-1)

更强大的版本也可以处理零和负值:

def required_steps(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 0
    return 1 + 2 * required_steps(n-1)

(添加非整数检查留作练习。)