如何编写一个递归函数来表示2的n次方减1？

Question

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

我需要一个递归函数，它接收参数n，并返回计算结果2ⁿ - 1。尽管看起来很简单，但这个函数要求使用递归实现。目前，我只有能够计算出2的n次方的函数：

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

练习题声明：“您可以假设参数n始终为正整数且大于0”

- Kajice

---

仅供参考，按照正常人的方式使用移位和减法应该更有效率。Python整数具有任意宽度，因此1 << n不会溢出。这似乎是一种将(1<<n)-1分解成多个步骤的练习，也许像某些答案所显示的那样，逐位设置每个位。 - Peter Cordes

def fn(n): if n == 0: return 1; return (2 << n) - fn(0); # 技术上是递归的请注意，此函数是一个计算机代码片段。它接受一个整数参数n，并返回一个数字结果。如果输入的n为零，则该函数将返回1。否则，函数将执行一些计算，然后通过调用它自己来递归地计算fn(0)，并将其结果从所得到的值中减去。具体而言，该函数将计算2左移n位的值（即2的n次方乘以2），然后从这个值中减去fn(0)的值。因此，函数本身必须能够处理所有可能的输入n值，并返回正确的结果。 - MooseBoys

@Voo: 不好意思，我不是Carl，但是请告诉我 C:\MyFolder 中包含了什么。 - Flater

@Voo：对于一个纯粹专注于教授递归概念的练习来说，依赖性与否并不重要。我可以创建一组基本的模拟类/方法供学生使用。你关注的是完全与练习重点无关的事情。使用文件系统导航是一个很好的例子，因为学生通常能理解文件夹和文件固有的递归性质（即文件夹可以相互嵌套到几乎无限深度）。 - Flater

@Voo 我的意思是，你可以通过展示一个递归数据结构来教授递归。我不知道为什么你很难理解这个概念。 - Flater

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)

（添加非整数的检查留作练习。）

- h4z3

---

required_steps(0) 现在会导致无限递归。 - Mulan

在那种情况下 2^0 - 1 等于 0。为这种情况添加另一个 if 语句。 - h4z3

是的，我知道什么是全函数。你呢？因为它永远不会成为全函数。其他答案也不是全函数。是的，需要更多的代码才能使它们成为全函数。正如我所说，我们没有域。我们应该假设我们的域是什么？即使只是“int”，当n＜0时，我们也不知道该做什么。计算？抛出错误？返回0？在这种情况下，我们只能做部分函数（为我们知道结果的事物定义函数）。 - h4z3

OP代码中的基本情况是“0”，并使用“n-1”作为子问题。自然数领域似乎很合适。 - Mulan

非常感谢！依我拙见，这是我特定问题的最佳解决方案。我没有说明 n 可能的取值，非常抱歉！我知道那很重要...该练习说明：“您可以假设参数 n 始终为正整数且大于 0”。 - Kajice

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

- blhsing

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

- rafaelc

Answer 4

有一个占位符来记住n的原始值，然后在第一步 n == N 中返回 2^n-1

n = 10
# constant to hold initial value of n
N = n
def required_steps(n, N):
    if n == 0:
        return 1
    elif n == N:
        return 2 * required_steps(n-1, N) - 1
    return 2 * required_steps(n-1, N)

required_steps(n, N)

- eMad

Answer 5

使用一个额外的参数来存储结果，r -

def required_steps (n = 0, r = 1):
  if n == 0:
    return r - 1
  else:
    return required_steps(n - 1, r * 2)

for x in range(6):
  print(f"f({x}) = {required_steps(x)}")

# f(0) = 0
# f(1) = 1
# f(2) = 3
# f(3) = 7
# f(4) = 15
# f(5) = 31

你也可以使用按位左移运算符<<来编写它 -

def required_steps (n = 0, r = 1):
  if n == 0:
    return r - 1
  else:
    return required_steps(n - 1, r << 1)

输出结果相同

- Mulan

---

简单的乘法练习不需要涉及位运算，这样做会让代码难以阅读。此外，在这两个函数中都不需要使用else子句。 - rafaelc

唯一的区别是将 r * 2 更改为 r << 1，这难道就“完全不可读”了吗？ - Mulan

发明第二个参数只会将其转换为一个循环，它向左移动n次，然后减去1。似乎比必要的还不够优雅，尽管整个过程是一种低效性与(1<<n) - 1之间的对比练习。 - Peter Cordes

@PeterCordes：将状态移入累加器参数是将递归调用转换为尾递归调用的标准方法。但不幸的是，Python 不支持 Proper Tail Calls，甚至不支持 Proper Tail Recursion，但这并不意味着学习这个有用技术没有意义，因为你可以在其他实现 Proper Tail Calls 或者至少 Proper Tail Recursion 的语言中应用它。 - Jörg W Mittag

@JörgWMittag 是的，但在这种情况下，循环更自然一些是很难掩饰的。也许只是因为我花了太多时间在汇编语言和性能方面，但在命令式语言中使用尾递归编写“循环”似乎是毫无意义的，而你可以直接编写一个循环。或者也许困扰我这个答案的只是如何分解的选择：先一个接一个地进行移位，然后再进行最终的减法操作作为基本情况。可能两者都有影响。 - Peter Cordes

Answer 6

除了之前提供的所有精彩答案，下面将展示如何使用内部函数实现。

def outer(n):
    k=n
    def p(n):
        if n==1:
            return 2
        if n==k:
            return 2*p(n-1)-1
        return 2*p(n-1)
    return p(n)

n=5
print(outer(n))

基本上，它将 n 的全局值赋给 k，并通过适当的比较进行递归处理。

- Your IDE

Answer 7

获取“-1”偏移量的一种方法是在第一个函数调用的返回值中使用具有默认值的参数，然后在递归调用期间显式地将偏移参数设置为零。

def required_steps(n, offset = -1):
    if n == 0:
        return 1
    return offset + 2 * required_steps(n-1,0)

- Eric Towers