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

Question

最近在研究递归；如何写，分析等等。我有一段时间认为递归和递归是同一件事，但最近作业和测验的一些问题让我觉得有细微的差别，“递归”是解决问题的方法。描述一个递归程序或函数。

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

那么，有几个问题:假设您遇到了这样的情况:

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

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

现在，假设您被要求查找递归 T(n)，以获取从前一个递归创建的程序执行的加法次数。我可以看到基本情况可能是 T(1) = T(2) = 0，但我不确定从哪里开始。

基本上，我问的是如何从给定的递归到代码，以及相反的情况。由于这看起来像主定理，我想知道是否有一种简单且数学的方法来解决它。

编辑:好的，我已经浏览了我过去的一些作业，以找到另一个例子，其中我被要求“找到重复”，这是我在帖子中遇到麻烦的问题的一部分.

Recurrence that describes in the best way the number of addition operations in the following program fragment (when called with l == 1 and r == n)

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 中的表达式进行积分。