从递归到迭代函数

Question

我正在尝试从 f_rec（递归函数）到 f_iter（迭代函数），但我做不到。（我的逻辑是创建一个循环来计算 f_rec(n-1).

的结果

int f_rec(int n)
{
 if(n>=3)
   return f_rec(n-1)+2*f_rec(n-2)+f_rec(n-3);
 else 
   return 1;
}

int f_iter(int n)
{
}

我也认为我的 f_rec 时间复杂度是 3^n ，如果我错了请指正。

谢谢

Answer 1

只保留三个变量并滚动它们

从a开始，b和c都等于1
每一步 new_a 是 a + 2*b + c
翻滚：new_c是b，new_b是a
重复所需的步数

Answer 2

您始终可以从最后三个值中计算出最新值。从头开始计算并始终保存最后三个：

int f_iter (int n) {
    int last3[3] = {1,1,1};  // The three initial values. Use std::array if C++

    for (int i = 3; i <= n; ++i) {
        int new_value = last3[0] + 2 * last3[1] + last3[2];
        last3[0] = last3[1];
        last3[1] = last3[2];
        last3[2] = new_value;
    }
    return last3[2];
}

此解决方案需要 O(1) 内存和 O(n) 运行时间。可能存在一个在 O(1) 中计算这个的公式（很可能是），但我想为了演示迭代技术，这是要走的路。

您的解决方案具有指数运行时间：每增加一个级别都会产生三个评估，因此您最终会得到 O(3^n) 操作和堆栈内存。

Answer 3

以下是思路

  int first=1,second=1,third=1; /* if n<=3 then the respective is the answer */
  for(i=4;i<=n;i++)
  {
     int next=first+2*second+third;
     first=second;
     second=third;
     third=next;
  }
  cout<<"The answer is "<<next<<endl;

内存是 O(1) 时间是 O(n).

编辑你的递归函数在时间上确实是指数的，为了保持它的线性，你可以使用数组 F[n]，并使用记忆。首先初始化F[]为-1.

    int f_rec(int n)
    {
        if(n>=3)
        {
           if(F[n]!=-1)return F[n];

           F[n]=f_rec(n-1)+2*f_rec(n-2)+f_rec(n-3);
           return F[n];       
        }  

        else 
           return 1;

}

Answer 4

有两种选择：

1) 利用离散数学课推导公式。内存和算法的复杂性（如果@Sasha 提到它的话）将为 O(1)。没有循环，没有递归，只有公式。

首先你需要找到特征多项式并计算它的根。假设我们的根是 r1、r2、r3、r4。那么第n个元素就是F(n) = A * r1^n + B * r2^n + C * r3^n + D * r4^n，其中A、B、C、D是一些未知的系数。您可以使用初始条件找到这些系数（F(n) = 1 for n <= 3）。

如果你需要，我可以用俄语解释。

2) 使用额外的变量来存储中间值。就像@6052 已经回答了一样（他回答的真快:)）。

Answer 5

有点矫枉过正，但这可以通过让变量代表的内容在展开的循环中发生变化，结合 (link) Duff's device 进入循环来进一步优化：

int f_iter(int n){
int a=1, b=1, c=1;
    if(n < 3)
        return(1);
    switch(n%3){
        for( ; n > 2; n -= 3){
            case 2:
                b = c + 2*a + b;
            case 1:
                a = b + 2*c + a;
            case 0:
                c = a + 2*b + c;
        }
    }
    return c;
}

从递归到迭代函数

From Recursive To Iterative Function

c

recursion