c++ - 如何计算递归结构？

Question

你能告诉我我们如何计算递归值吗？

例如以下递归函数：

int rec (int n)
{
    if (n==1) return (1);
    else  
        return (rec(n-1) + rec(n-1));
}

有没有解决这类问题的一般线索？

Answer 1

好吧，让我们先把它写成

int rec (int n)
{
  if (n==1) return (1);
  else  
    return (2 * rec(n-1));
}

作为a+a = 2a

接下来我们看到将 2 相乘n-1，第 n 次返回 1。

因此这相当于 2^(n-1)

这意味着rec(5) = 2^(5-1) = 2^4 = 16

注意：我上面的表格也比你的表格更有效率，因为我只计算rec(n-1) rec(n-2)一次，依此类推（线性递归）。与您的函数一样，每个函数都以指数方式计算多次（指数递归）。这意味着虽然我的函数可以很好地扩展，但你的函数基本上不能用于大于 100 的任何东西。