如何使用Master定理来描述递归？

Question

最近我一直在研究递归;如何编写，分析等等。我曾经想过一段时间，递归和递归是同一回事，但是最近的家庭作业和测验中的一些问题让我觉得存在细微的差异，'重现'是描述一个递归程序或函数。

直到最近，当我意识到存在一种被称为'主定理'的问题或程序的'复发'时，这一直都是非常希腊的东西。我一直在阅读维基百科页面，但像往常一样，事情的措辞使我不明白它在说什么。我用例子学得更好。

所以，有几个问题： 可以说，你给出这样的复发：

R（N）= 2 * R（N-2）+ R（N-1）;
R（1）= R（2） = 1

这是，实际上，在主定理的形式？如果是这样，用言语来说，它是什么意思？如果您想要基于这种重现编写一个小程序或一个递归树，那会是什么样子？我应该试着用数字替换数字，看一个模式，然后编写可以递归地创建该模式的伪代码，或者，因为这可能是主定理的形式，是否有更直接的数学方法？

现在，让我们说你被要求找到重复T（n），用于从先前的重复创建的程序执行的重复次数。我可以看到基本情况可能是T（1）= T（2）= 0，但我不确定从那里去哪里。

基本上，我问的是如何从一个给定的循环到代码，而相反。既然这看起来像大师定理，我想知道是否有一个简单而直接的数学方法去实现它。

编辑：好吧，我已经浏览了我过去的一些作业，以找到另一个我被问到的例子，'找到复发'，这是这个问题的一部分，我有后期的麻烦用。

复发，在最佳 方式描述了加法运算的 下面的程序片段

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

Answer 1

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

见，例如，该新手必看：http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

基本上，让您的复发看起来像式（1）中的文件，摘掉系数，并表达整合定理1

Answer 2

（当以L == 1和R ==ñ调用）的数量你方法，使用递归函数代码写的，应该是这样的：

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 
} 

我不是苏re是什么“复发”，但递归函数只是一个自称的函数。

递归函数需要一个转义子句（一些非递归情况下 - 例如，“如果n == 1返回1”），以防止一个堆栈溢出误差（即，该函数被调用这么多的解释程序运行内存或其他资源）

Answer 3

一个简单的程序，将实现一个看起来像：

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

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

Answer 4

“我并不完全相信‘复发’是不是”

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

而且，我认为解决它们的目标是从递归定义转到不是。假如你对所有n> 0有T（0）= 2和T（n）= 2 + T（n-1），你必须从表达式“T（n）= 2 + T（n -1）“与”2n + 2“之一相同。

来源： 1） “与图论离散数学 - 第二版”，由Edgar G. GOODAIR和Michael M.帕门 2） “计算机算法C++”，由埃利斯维茨，萨尔塔杰尼，和Sanguthevar Rajasekaran。

Answer 5

扎卡里：

比方说你给出此 复发：

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

对于 '一' 和 'b' 是一些常数，f（n）是n个某些功能。在你的陈述中，a = 1，b = 2和f（n）= 0。每当f（n）等于零时，递归关系就称为“同质的”。所以，你的表情是同质的。

因为f（n）= 0，所以我不认为你可以使用主方法Theoerm求解同质递归关系。主方法定理没有一种情况允许这样做，因为n-to-the-power-任何东西都不能等于零。我可能是错的，因为我不是这方面的专家，但我不认为有可能使用主方法解决同质复发关系。

我认为，要解决均匀递推关系的方法是通过5个步骤走：

1）形式特征方程，这是形式的东西：

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

如果您“VE只在您的同质递推关系得到了2种递归的情况下，那么你只需要改变你的方程为二次方程，其中

x^2 - a*x - b = 0 

这是BEC澳洲英语的

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]，你的soluti对具有以下形式：

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 ] 

扎卡里：

复发，在最好 方式描述了加法运算的在下面的程序片段 数（当与升== 1和r == N）

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

在这里称为了给定代码的时间复杂度的值在r> 1：

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 ==升则T（R）= 2，因为if语句和返回都需要1步每次执行。