Do iterative and recursive versions of an algorithm have the same time complexity?

Question

Say, for example, the iterative and recursive versions of the Fibonacci series. Do they have the same time complexity?

Answer 1

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

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[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.