我如何使用主定理描述递归？

Question

最近我一直在学习递归，如何编写、分析等。我曾经认为递归和循环是同一回事，但最近的作业和测验问题让我想到了细微之处，即“递归”是描述程序或函数的方式。

这对我来说一直很难理解，直到最近我才意识到有一个被称为“主定理”的东西可用于写出问题或程序的“递归”。我一直在阅读维基百科页面，但通常情况下，其中的措辞让我无法真正理解它在说什么。我更喜欢通过例子来学习。

所以，有几个问题： 假设您得到了这个递归式：

r(n) = 2*r(n-2) + r(n-1); r(1) = r(2) = 1

请问这是否实际上符合主定理的形式？如果是，换句话说，它在说些什么？如果您正在尝试编写一个基于此递归式的小程序或递归树，那会是什么样子？我应该尝试替换数字，看看模式，然后编写能够递归创建该模式的伪代码，还是因为这可能符合主定理的形式，有更简单、数学的方法？

现在，假设您被要求找出从以前的递归式创建的程序执行的加法次数的递归式T(n)。我可以看到基本情况可能是T(1)=T(2)=0，但不确定该如何继续。

基本上，我想知道如何从给定的递归式转换为代码，反之亦然。既然这看起来像主定理，我想知道是否有一种简单而数学的方法。

编辑：好吧，我查看了一些过去的作业，找到了另一个例子，即让我“找到递归”的部分，这是我在这个问题中遇到麻烦的地方。

描述以下程序片段（当用l==1和r==n调用时）中执行加法操作数量的最佳递归

int example(A, int l, int r) {
  if (l == r)
    return 2;
  return (A[l] + example(A, l+1, r);
}

- Zachary

Answer 1

几年前，Mohamad Akra和Louay Bazzi证明了一个推广了Master方法的结果 - 它几乎总是更好。你真的不应该再使用Master定理了...例如，参见这篇文章：http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf 基本上，让您的递归看起来像论文中的方程式1，挑选系数，并在定理1中积分表达式即可。

- Ying

Answer 2

Zachary:

假设你得到了这个递归式：

r(n) = 2*r(n-2) + r(n-1); r(1) = r(2) = 1

这是否符合主定理的形式？如果是，用简单易懂的语言说明它的含义。

我认为你的递归关系所表达的意思是，对于一个以“r”为函数、以“n”为参数的函数（表示输入数据集的总数），在第n个位置得到的任何结果都是n-1位置的输出加上两倍n-2位置的结果，而没有进行非递归工作。当你试图解决递归关系时，你要尝试以不涉及递归的方式来表达它。

但是，我认为这并不符合主定理方法的正确形式。你的陈述是一个“具有常数系数的二阶线性递归关系”。根据我旧的离散数学教科书的说法，这是你需要拥有的形式，以便解决递归关系。

这里是他们给出的形式：

r(n) = a*r(n-1) + b*r(n-2) + f(n)

对于一些常量'a'和'b'，以及函数f(n)，当f(n)等于0时，递归关系被称为“齐次”的。在您的语句中，a=1，b=2，f(n)=0。因此，您的表达式是齐次的。

我认为您无法使用主方法定理解决齐次递归关系，因为f(n) = 0。主方法定理中的任何情况都不允许这种情况发生，因为n的任何幂都不能等于0。虽然我不是专家，但我认为无法使用主方法解决齐次递归关系。

我认为解决齐次递归关系的方法是按照以下5个步骤进行：

1）形成特征方程，其形式如下：

x^k - c[1]*x^k-1 - c[2]*x^k-2 - ... - c[k-1]*x - c[k] = 0

如果你的同次递归关系中只有两个递归实例，那么你只需要将方程改为二次方程，其中

x^2 - a*x - b = 0

这是因为一个形如的递归关系式：

r(n) = a*r(n-1) + b*r(n-2)

可以重写为

r(n) - a*r(n-1) - b*r(n-2) = 0

2) 在将您的递归关系重写为特征方程之后，接下来找到特征方程的根（x[1]和x[2]）。

3) 有了您的根，您的解现在将是以下两种形式之一：

if x[1]!=x[2]
    c[1]*x[1]^n + c[2]*x[2]^n
else
    c[1]*x[1]^n + n*c[2]*x[2]^n

针对n>2的情况，你可以使用新形式的递归解法，使用初始条件（r(1)和r(2)）来找到c[1]和c[2]。

以你的例子为例，我们得到：

1) r(n) = 1*r(n-1) + 2*r(n-2) => x^2 - x - 2 = 0

2) 解方程得到x

x = (-1 +- sqrt(-1^2 - 4(1)(-2)))/2(1)

    x[1] = ((-1 + 3)/2) = 1
    x[2] = ((-1 - 3)/2) = -2

3) 由于x[1] != x[2]，你的解决方案应该是这样的：

c[1](x[1])^n + c[2](x[2])^n

4) 现在，使用您的初始条件来找到两个常数c [1]和c [2]:

c[1](1)^1 + c[2](-2)^1 = 1
c[1](1)^2 + c[2](-2)^2 = 1

诚实地说，在这种情况下，我不确定您的常数是什么，我在这一点上停止了。我想您需要插入数字，直到您以某种方式得到c [1]和c [2]的值，这两个值都满足这两个表达式。除此之外，您还可以对矩阵C执行行约简，其中C等于：

[ 1 1   | 1 ]
[ 1 2   | 1 ] 

扎卡里：

以下程序片段（当l == 1且r == n时调用）中描述加法操作数量的最佳递归方式

int example(A, int l, int r) {
  if (l == r)
    return 2;
  return (A[l] + example(A, l+1, r);
}

以下是当 r > l 时给定代码的时间复杂度值：

int example(A, int l, int r) {      =>  T(r) = 0
  if (l == r)               =>  T(r) = 1
    return 2;               =>  T(r) = 1
  return (A[l] + example(A, l+1, r);    =>  T(r) = 1 + T(r-(l+1))
}

Total:                      T(r) = 3 + T(r-(l+1))

否则，当r==l时，T(r) = 2，因为if语句和return语句每次执行都需要1步。

- Michael M. Adkins

Answer 3

你的方法，使用递归函数编写的代码，看起来像这样：

function r(int n) 
{
  if (n == 2) return 1;
  if (n == 1) return 1;
  return 2 * r(n-2) + r(n-1);  // I guess we're assuming n > 2
}

我不确定 "recurrence" 是什么意思，但递归函数就是一个调用自己的函数。

递归函数需要一个“退出条件”（一些非递归情况 - 例如，“如果 n==1，则返回 1”），以防止发生“堆栈溢出”错误（即该函数被调用太多次，解释器会耗尽内存或其他资源）。

- David

---

好的，这似乎很简单。我也不太确定“recurrence”是什么意思，但我的教授经常使用这个词，而且练习测试中有几道题要求我们查找程序中的“recurrence”。我会在我的问题中编辑另一个例子。 - Zachary Wright

Answer 4

一个简单的实现该功能的程序可能如下所示：

public int r(int input) {
    if (input == 1 || input == 2) {
        return 1;
    } else {
        return 2 * r(input - 2) + r(input -1)
    }
}

你还需要确保输入不会导致无限递归，例如，如果一开始的输入小于1。如果这不是一个有效的情况，则返回错误，如果是有效的情况，则返回相应的值。

- Elie

Answer 5

我也不确定“recurrence”是什么意思。

“递归关系”的定义是一组数字序列，“其定义域为某个无限整数集合，其值域为一组实数。”另外，描述该序列的函数“以前一个成员为基础定义下一个成员。”

解决这些问题的目标，我认为，是从递归定义转换为非递归定义。例如，如果您有T(0) = 2和T(n) = 2 + T(n-1)（n>0），则必须从表达式“T(n) = 2 + T(n-1)”转换为“2n+2”之类的表达式。

参考资料： 1）《离散数学与图论-第二版》，作者：Edgar G. Goodair和Michael M. Parmenter 2）《计算机算法C++》，作者：Ellis Horowitz、Sartaj Sahni和Sanguthevar Rajasekaran。

- Michael M. Adkins