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

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).