6

最近一直在研究递归；怎么写，怎么分析等等。我一直认为递归和递归是一回事，但是最近的家庭作业和测验中的一些问题让我觉得有细微的差别，“递归”是一种方法描述递归程序或函数。

直到最近，这对我来说都是非常希腊化的，当我意识到有一种叫做“主定理”的东西用来写问题或程序的“递归”时。我一直在阅读维基百科页面，但是，像往常一样，事情的措辞让我真的不明白它在说什么。我通过例子学得更好。

所以，有几个问题：假设你得到了这个重复：

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);
}
4

5 回答 5

8

几年前，Mohamad Akra 和 Louay Bazzi 证明了一个推广 Master 方法的结果——它几乎总是更好。你真的不应该再使用主定理了......

例如，参见这篇文章：http: //courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

基本上，让你的递归看起来像论文中的等式 1，挑选系数，并整合定理 1 中的表达式。

于 2008-10-20T17:43:43.590 回答
2

扎卡里：

假设你得到了这个重复：

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

这实际上是主定理的形式吗？如果是这样，用语言来说，它在说什么？

我认为你的递归关系所说的是，对于以“n”为参数的“r”函数（代表你输入的数据集的总数），无论你在数据集的第 n 个位置得到什么是第 n-1 个位置的输出加上第 n-2 个位置的结果的两倍，没有进行非递归工作。当您尝试解决递归关系时，您正在尝试以不涉及递归的方式表达它。

但是，我认为这不是主定理方法的正确形式。您的陈述是“具有恒定系数的二阶线性递推关系”。显然，根据我的旧离散数学教科书，这是解决递归关系所需的形式。

这是他们提供的表格：

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

因为'a'和'b'是一些常数，f(n)是n的一些函数。在您的陈述中，a = 1、b = 2 和 f(n) = 0。只要 f(n) 等于零，递归关系就称为“同质”。所以，你的表达是同质的。

我不认为你可以使用主方法定理来解决同质递归关系，因为 f(n) = 0。主方法定理的任何情况都不允许这样做，因为任何事物的 n-to-the-power-of-anything 都可以'不等于零。我可能是错的，因为我不是这方面的专家，但我不认为使用主方法解决同质递归关系是可能的。

我认为解决齐次递推关系的方法是通过 5 个步骤：

1) 形成特征方程，其形式为：

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

如果您的齐次递归关系中只有 2 个递归实例，那么您只需将方程更改为二次方程，其中

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 时。4) 使用新形式的递归解决方案，您可以使用初始条件（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 步。

于 2010-08-13T05:44:19.743 回答
1

您的方法使用递归函数以代码编写，如下所示：

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
}

我不确定“递归”是什么，但递归函数只是一个调用自身的函数。

递归函数需要一个转义子句（一些非递归情况 - 例如，“如果 n==1 返回 1”）以防止堆栈溢出错误（即，函数被调用太多以至于解释器内存不足或其他资源）

于 2008-10-20T17:31:41.617 回答
1

一个可以实现的简单程序如下所示：

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

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

于 2008-10-20T17:34:20.690 回答
1

“我也不完全确定‘复发’是什么”

“递归关系”的定义是一个数字序列，“其域是一些无限的整数集，其范围是一组实数。” 附加条件是描述此序列的函数“根据前一个成员定义序列的一个成员”。

而且，我认为，解决它们背后的目标是从递归定义变为非递归定义。假设你有 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) Ellis Horowitz、Sartaj Sahni 和 Sanguthevar Rajasekaran 的“计算机算法 C++”。

于 2010-08-11T23:22:28.460 回答