基本操作的递归关系

Question

我需要一些帮助来为以下递归算法的基本操作创建递归关系：

int D(int n) {
  if (n==0) {
    return 0;
  }
  return D(n - 1) + D(n - 1);
}

我认为这个的基本操作是加法，但我在设置递推关系时遇到了问题

Answer 1

您确定这是正确的代码吗？递推关系为

D(n) = 2 * D(n-1)
base case D(n) = 0

你知道这是怎么回事吗？该函数的递归步骤向您显示递归步骤；该函数的终止子句显示了基本情况。

我很担心，因为在封闭形式中，这是

D(n) = 0 for all n

Recurrence relation for basic operation