python - 嵌套递归是可能的还是我们应该避免递归？

Question

遇到这样的问题

• F(1) = 1
• F(2n) = F(n)
• F(2n+1) = F(n) + F(n+1)

开发一个递归程序来计算F

一些用户提到使用两个递归函数调用:

def calc(n):
  if n=1 :
    return 1
  else if(n%2)==0:
    return calc(n/2)
  else :
    return calc(n/2)+calc(n/2+1)  **NESTED RECURSION**

这是一个正确的逻辑吗？算法不会呈指数级增长吗？我想到了一个简单的代码，例如:

def calc(count):
  result[1]=1
  n=2
  for range(1,count):
      if n%2=0:
          result.append(result[n])
      else :
          result.append(result[n/2]+result[n/2+1])
  return result

Answer 1

这两种方法都是正确的。从一个函数进行多次递归调用确实是合法的，其含义就是您所想的 - 只需执行一次调用，然后进行下一次调用，然后进行下一次调用，依此类推。

有趣的是，我不认为递归版本会进行指数级的多次调用。它最多进行两次递归调用，但每个递归调用的大小(大约)是原始调用的一半。本质上，重复看起来像这样:

T(1) = 1
T(2) = 1
T(n) <= T(n / 2) + T(n / 2 + 1) + 1

我用“小于或等于”来表示在最好的情况下你可能只打一个电话，但在最坏的情况下你最多打两个电话。

我想证明这个函数 T(n) <= max{cn + d, a} 对于一些常量 c、d 和 a。这将证明 T(n) = O(n)，因此至多进行线性多次调用。作为我们的基本案例，我们有这样的

T(1) = 1
T(2) = 1

所以让我们设置 a = 1。对于归纳步​​骤，我们考虑三种情况。首先，让我们考虑一下 floor(n/2) <= 2 和 floor(n/2 + 1) <= 2 的情况:

T(n) <= T(n / 2) + T(n / 2 + 1) + 1
     <= 1 + 1 + 1
     <= 3

如果我们假设 cn + d >= 3，当 n = 3 或 n = 4 时，则计算正确。特别是，这意味着 3c + d >= 3 和 4c + d >= 3。

在下一种情况下，让我们看看如果 floor(n/2) <= 2 且 floor(n/2 + 1) >= 2 会发生什么。然后我们就有了

T(n) <= T(n / 2) + T(n / 2 + 1) + 1
     <= 1 + max{c(n / 2 + 1) + d, 1} + 1
     <= 2 + max{c(n / 2 + 1) + d, 1}
     <= 3 + c(n / 2 + 1) + d

所以如果我们有 3 + c(n/2 + 1) + d <= cn + d，这个说法仍然成立。请注意，我们仅在这种情况下 n = 5，因此这意味着我们必须拥有它

3 + c(n / 2 + 1) + d <= cn + d
3 + c(n / 2 + 1)     <= cn
3 + c(5 / 2 + 1)     <= 5c
3 + 5c/2 + c         <= 5c
3 + 7c/2             <= 5c
4                    <= 3c / 2
8 / 3                <= c

所以我们必须有 c >= 8/3。

最后，n/2 和 n/2 + 1 都不小于三的情况:

T(n) <= T(n / 2) + T(n / 2 + 1) + 1
     <= c(n / 2) + d + c(n / 2 + 1) + d + 1
     <= cn / 2 + cn / 2 + c + 2d + 1
      = cn + c + 2d + 1

这小于 cn + d 如果

 cn + c + 2d + 1 <= cn + d
      c + 2d + 1 <=      d
      c +  d + 1 <= 0

这在 d = -c - 1 时有效。

从前面，我们知道 3c + d >= 3，如果 2c - 1 >= 3，或者 2c >= 4，所以 c >= 2。我们还有 4c + d >= 3，这如果 c >= 2 也有效。让 c = 8/3，我们得到 d = -11/3，所以

T(n) <= max{8n/3 - 11/3, 1}

因此 T(n) = O(n) 并且递归仅进行线性多次调用。

---

这个的简短版本是递归和迭代版本都需要线性时间。在不确定递归是指数级的情况下，不要害怕递归的指数时间爆炸。 :-) 虽然不可否认，在这种情况下，我真的更喜欢迭代版本。它更清晰、更直观、更即时 O(n)。