如何写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保证大于零（如问题声明中实际承诺的那样），则此方法有效：

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)

（剩下的是对非整数的检查作为练习。）

Answer 2

要使用递归方法解决问题，您将必须找出如何根据给定输入的功能定义相同输入和不同输入的功能。在这种情况下，由于f(n) = 2 * f(n - 1) + 1，您可以执行以下操作：

def required_steps(n):
    return n and 2 * required_steps(n - 1) + 1

以便：

for i in range(5):
    print(required_steps(i))

输出：

0
1
3
7
15

Answer 3

您可以将真正的递归部分提取到另一个函数中

def f(n):
    return required_steps(n) - 1

或者您可以设置一个标志并定义何时减去

def required_steps(n, sub=True):
    if n == 0: return 1
    return 2 * required_steps(n-1, False) - sub

>>> print(required_steps(10))
1023