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

Question

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

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

那么如何纠正我的代码以实现我的目标呢？

Answer 1

通过一般的转换迭代来解决这个问题是一个坏主意.但是,这就是你的要求.

这些都不是解决的好方法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;
}

现在创建一个循环.而不是递归调用,设置你 的返回位置,用一个和一个位置fib_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;
  }
}

然后注意b并且r不必在堆栈中 - 删除它,并使其成为本地.

这种"愚蠢"的转换模仿了你递归时C++编译器的作用,但是堆栈存储在免费存储而不是自动存储中,并且可以重新分配.

如果指向局部变量的指针需要持久化,则使用std::vector堆栈的指针将不起作用.将带有偏移的指针替换为标准向量,它将起作用.