无论是两种算法的迭代和递归版本具有相同的复杂性？例如说斐波那契数列的迭代和递归版本。

Whether the iterative and recursive versions of two algorithms have same complexity? Say for example the iterative and recursive versions of Fibonacci series.

推荐答案

答案很大程度上取决于您的实现。因为你给的例子有几个可能的解决方案，我会说，实现解决方案的原始的方法具有更好的复杂性时，执行迭代。这里有两种实现方式：

The answer depends strongly on your implementation. For the example you gave there are several possible solutions and I would say that the naive way to implement a solution has better complexity when implemented iterative. Here are the two implementations:

int iterative_fib(int n) {
   if (n <= 2) {
     return 1;
   }
   int a = 1, int b = 1, c;
   for (int i = 0; i < n - 2; ++i) {
     c = a + b;
     b = a;
     a = c;
   }
   return a;
}
int recursive_fib(int n) {
  if (n <= 2) {
    return 1;
  }
  return recursive_fib(n - 1) + recursive_fib(n-2);
}

在两种实现我承担了正确的输入，即N> = 1。第一code是更长的时间，但其复杂度为O（n），即线性的，而第二个实施较短，但具有指数复杂度为O（FIB （N））= 0（φ^ n）的（φ=（1 +√5）/ 2 ），因此要慢得多。 一个可以提高递归版本通过引入记忆化（即记住你已经计算的函数的返回值）。这通常是通过介绍您存储的值的数组实现。下面是一个例子：

In both implementations I assumed a correct input i.e. n >= 1. The first code is much longer but its complexity is O(n) i.e. linear, while the second implementation is shorter but has exponential complexity O(fib(n)) = O(φ^n) (φ = (1+√5)/2) and thus is much slower. One can improve the recursive version by introducing memoization(i.e. remembering the return values of the function you have already computed). This is usually done by introducing an array where you store the values. Here is an example:

int mem[1000]; // initialize this array with some invalid value. Usually 0 or -1 
               // as memset can be used for that: memset(mem, -1, sizeof(mem));
int mem_fib(int n) {
  if (n <= 2) {
    return mem_fib[n] = 1;
  }
  if (mem[n-1] == -1) {
    solve(n-1);
  }
  if (mem[n-2] == -1) {
    solve(n-2);
  }
  return mem[n] = mem[n-1] + mem[n-2];
}

下面的递归算法的复杂度是线性就像迭代求解。我上面介绍的解决方案是你的问题的动态规划解自顶向下的方法。自底向上的方法会导致一些非常相似，我介绍了作为迭代解决方案。 有大量的动态规划文章，包括在维基

Here the complexity of the recursive algorithm is linear just like the iterative solution. The solution I introduced above is the top-down approach for dynamic programming solution of your problem. The bottom-up approach will lead to something very similar to the solution I introduced as iterative. There a lot of articles on dynamic programming including in wikipedia

根据我见过在我的经验有些方式很难与自下而上的方法来解决的问题（即迭代求解），而另一些难以解决与自上而下的方法。 然而，理论指出，具有迭代求解每个问题具有相同的计算复杂性（反之亦然）的递归

Depending on the problems I have met in my experience some are way harder to be solved with bottom-up approach(i.e. iterative solution), while others are hard to solve with top-down approach. However the theory states that each problem that has an iterative solution has a recursive with the same computational complexity (and vice versa).

希望这个答案可以帮助。

Hope this answer helps.