C语言 如何将递归转换为迭代求解

sulc1iza  于 11个月前  发布在  其他
关注(0)|答案(5)|浏览(135)

我已经设法用递归的方式写了我的算法:

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;
}


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

3z6pesqy

3z6pesqy1#

用一般的转换到迭代来解决这个问题是一个坏主意。但是,这就是你问的。
这些都不是解决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;
}


现在创建一个循环。而不是递归地调用,在 yourfib_data中设置返回位置,将fib_data推到带有ne0位置的堆栈上,然后继续循环。在循环的顶部,在堆栈位置的顶部切换。
返回:创建一个函数局部变量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;
  }
}


然后请注意,br不必在堆栈中--将其删除,并使其成为本地堆栈。
这种“哑”转换模拟了C++编译器在递归时所做的事情,但堆栈存储在自由存储区而不是自动存储区,并且可以重新分配。
如果指向局部变量的指针需要持久化,那么使用std::vector作为堆栈将不起作用。将指针替换为标准向量中的偏移量,它将起作用。

gtlvzcf8

gtlvzcf82#

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

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

字符串
或者你可以展开一点循环,去掉temp变量:

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;
}

svdrlsy4

svdrlsy43#

这是一个经典的问题,你不能简单地摆脱递归,如果你给定n,你想向下计算。
解决方案是动态编程。基本上你想创建一个大小为n的数组,然后从索引0开始填充它,直到索引n-1;
就像这样:

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];


}

csbfibhn

csbfibhn4#

这样的话,时间复杂度为O(1):

int fib(n)
{
    int i;
    int a0 = 3;
    int a1 = 2;
    int tmp;

    if (n == 1)
        return a0;

    for (i = 3; i <=n; i++ )
    {
        tmp = a0 + a1;
        a0 = a1;
        a1 = tmp;
    }
    return a1;
}

字符串

ltqd579y

ltqd579y5#

条件if (n == 1)if (n == 2)应该放在循环之外,因为它们是不依赖于循环变量的特殊情况,你的循环应该从k = 3开始,因为n = 1n = 2的斐波那契序列是分开处理的,然后我们可以从n = 3开始构建序列。
以下循环是迭代计算斐波那契序列的更新方法,在每次迭代中更新ij

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;
}

字符串

相关问题