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

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

型

这是一个经典的问题，你不能简单地摆脱递归，如果你给定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];

型
}

这样的话，时间复杂度为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;
}

字符串

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

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

字符串