如何将递归解决方案转换为迭代解决方案

问题描述 投票：0回答：5

我已经设法以递归方式编写我的算法：

int fib(int n) {
    if(n == 1)
        return 3
    elseif (n == 2)
        return 2
    else
        return fib(n – 2) + fib(n – 1)
}

目前我正在尝试将其转换为迭代方法，但没有成功：

int fib(int n) {
   int i = 0, j = 1, k, t;
   for (k = 1; k <= n; ++k)
   {
       if(n == 1) {
           j = 3;
       }
       else if(n == 2) {
           j = 2;
       }
       else {
           t = i + j;
           i = j;
           j = t;
       }
   }
   return j;
}

那么我该如何纠正我的代码以达到我的目标？

c++ c algorithm recursion fibonacci
5个回答
7
投票

通过一般的转换为迭代来解决这个问题是一个坏主意。但是，这就是你问的。

这些都不是解决

fib
的好方法：对于
fib
有封闭形式的解决方案，和/或更干净的迭代解决方案，和/或递归记忆解决方案。相反，我展示的是相对“机械”的技术，用于采用递归函数（不是尾递归或其他简单的解决方案），并在不使用自动存储堆栈（递归）的情况下解决它。 我的代码执行了太深的递归嵌套，并在中高复杂度的情况下破坏了堆栈；当重构为迭代时，问题就消失了。当您所拥有的是您“一半”理解的递归解决方案并且您需要它是迭代的时，需要这些解决方案。

将递归解决方案转换为迭代解决方案的一般方法是手动管理堆栈。

在这种情况下，我还将记住返回值。

我们将返回值缓存在

retvals

中。

如果我们不能立即解决问题，我们会说明我们首先需要解决哪些问题才能解决我们的问题（特别是 n-1 和 n-2 情况）。然后我们再次排队解决我们的问题（此时，我们将准备好我们需要的东西）。
int fib( int n ) { std::map< int, int > retvals { {1,3}, {2,2} }; std::vector<int> arg; arg.push_back(n); while( !arg.empty() ) { int n = arg.back(); arg.pop_back(); // have we solved this already? If so, stop. if (retvals.count(n)>0) continue; // are we done? If so, calculate the result: if (retvals.count(n-1)>0 && retvals.count(n-2)>0) { retvals[n] = retvals[n-1] + retvals[n-2]; continue; } // to calculate n, first calculate n-1 and n-2: arg.push_back(n); arg.push_back(n-1); arg.push_back(n-2); } return retvals[n]; }

没有递归，只是一个循环。

执行此操作的一种“愚蠢”方法是获取该函数并将其设为伪协程。

首先，重写递归代码以每行执行一件事：

int fib(int n) { if(n == 1) return 3 if (n == 2) return 2 int a = fib(n-2); int b = fib(n-1); return a+b; }

接下来，创建一个包含所有函数状态的结构体：

struct fib_data {
  int n, a, b, r;
};

并在我们进行递归调用的每个点添加标签，以及具有相似名称的枚举：

enum Calls {
  e1, e2
};
int fib(int n) {
  fib_data d;
  d.n = n;

  if(d.n == 1)
    return 3
  if (d.n == 2)
    return 2
  d.a = fib(n-2);
CALL1:
  d.b = fib(n-1);
CALL2:
  d.r = d.a+d.b;
  return d.r;
}

将

CALLS
 添加到您的
fib_data

。
接下来创建一堆
fib_data
：

enum Calls { e0, e1, e2 }; struct fib_data { Calls loc = Calls::e0; int n, a, b, r; }; int fib(int n) { std::vector<fib_data> stack; stack.push_back({n}); if(stack.back().n == 1) return 3 if (stack.back().n == 2) return 2 stack.back().a = fib(stack.back().n-2); CALL1: stack.back().b = fib(stack.back().n-1); CALL2: stack.back().r = stack.back().a + stack.back().b; return stack.back().r; }
现在创建一个循环。不要递归调用，而是在

your
fib_data

中设置返回位置，将 fib_data 与 

n
和 
e0
位置一起推入堆栈，然后继续循环。在循环的顶部，切换堆栈顶部的位置。
返回：创建一个函数局部变量r来存储返回值。要返回，请设置 
r
，弹出堆栈，然后继续循环。

如果循环开始时堆栈为空，则从函数返回 

r
。

enum Calls { e0, e1, e2 }; struct fib_data { int n, a, b, r; Calls loc = Calls::e0; }; int fib(int n) { std::vector<fib_data> stack; stack.push_back({n}); int r; while (!stack.empty()) { switch(stack.back().loc) { case e0: break; case e1: goto CALL1; case e2: goto CALL2; }; if(stack.back().n == 1) { r = 3; stack.pop_back(); continue; } if (stack.back().n == 2){ r = 2; stack.pop_back(); continue; } stack.back().loc = e1; stack.push_back({stack.back().n-2}); continue; CALL1: stack.back().a = r; stack.back().loc = e2; stack.push_back({stack.back().n-1}); continue; CALL2: stack.back().b = r; stack.back().r = stack.back().a + stack.back().b; r = stack.back().r; stack.pop_back(); continue; } }
然后请注意，

b
和
r

不必位于堆栈中——将其删除，并将其设置为本地。
这种“哑”转换模拟了 C++ 编译器在递归时所做的操作，但堆栈存储在自由存储中而不是自动存储中，并且可以重新分配。
如果指向局部变量的指针需要保留，则对堆栈使用

std::vector

将不起作用。将指针替换为标准向量中的偏移量，这样就可以工作了。

这应该是 fib(0) = 0、fib(1) = 1、fib(2) = 1、fib(3) = 2、fib(4) = 3、fib(5) = 5、fib(6) = 8，....




      

      
      
      

      

        

          

            

              
3
投票

              
            

          

        

        



或者你可以稍微展开循环，并去掉临时变量：



int fib(int n)
{
int f0, f1;
    if(n < 2)
        return n;
    f0 = 1-(n&1);
    f1 = 1;
    while(0 < (n -= 2)){
        f0 += f1;
        f1 += f0;
    }
    return f1;
}


    




这是一个经典问题。如果给定 n 并且你想向下计算，你不能简单地摆脱递归。 




      

      
      
      

      

        

          

            

              
2
投票

              
            

          

        

        



类似这样的：



int fib(int n)
{
    int buffer[n+1];
    buffer[0]=3;
    buffer[1]=2;
    for(int i=2;i<=n; ++i)
    {
        buffer[i] = buffer[i-1] + buffer[i-2];
    }

    return buffer[n];
}




或者为了节省内存而不使用大数组，您可以使用：



int fib(int n)
{
    int buffer [2];
    buffer[0] = 3;
    buffer[1] = 2;


    for(int i=3; i<=n; i++)
    {
    int tmp = buffer[0] + buffer[1];
    buffer[0] = buffer[1];
    buffer[1] = temp;
    }

    return buffer[1];




}

    


为了完整起见，这里是空间复杂度为 O(1) 的迭代解决方案：




      

      
      
      

      

        

          

            

              
1
投票

              
            

          

        

        

    




条件 if (n == 1) 和 if (n == 2) 应该放在循环之外，因为它们是不依赖于循环变量的特殊情况，循环应该从 k = 3 开始，因为斐波那契数列n = 1 和 n = 2 的序列是分开处理的，然后我们可以从 n = 3 开始构建序列。



      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


    int fib(int n) {
       if (n == 1) 
           return 3;
       else if (n == 2) 
           return 2;
         

       int i = 0, j = 1, k, t;
       for (k = 3; k <= n; ++k) {
           t = i + j;
           i = j;
           j = t;
       }
       return j;
     }


    



      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.