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

最近我一直在研究递归; 如何写它,分析它等等我曾经想过复发和递归是一回事,但是最近的家庭作业和测验中的一些问题让我觉得有一些细微的差别,"复发"是通往描述递归程序或函数.

直到最近,当我意识到有一些叫做"主要定理"的东西用来为问题或程序写出"重现"时,这对我来说都是非常希腊的.我一直在阅读维基百科页面,但是,像往常一样,事情的措辞是这样的,我并不真正理解它在谈论什么.我通过实例了解得更多.

所以,有几个问题:让我们说你再次发生这种情况:

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

Ying Xiao.. 8

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

例如,请参阅此文章:http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

基本上,让你的重复看起来像论文中的方程式1,选择系数,并将表达式集成在定理1中.

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

例如,请参阅此文章:http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

基本上,让你的重复看起来像论文中的方程式1,选择系数,并将表达式集成在定理1中.