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.

Answer 2

The particular recursive algorithm for calculation fibanocci series is less efficient. Consider the following situation of finding fib(4) through the recursive algorithm

                int fib(n) :
                        if( n==0 || n==1 )
                            return n;
                        else
                            return fib(n-1) + fib(n-2)

Now when the above algorithm executes for n=4

                            fib(4)

                    fib(3)             fib(2)

                fib(2)   fib(1)     fib(1)   fib(0)

             fib(1)  fib(0) 

It's a tree. It says that for calculating fib(4) you need to calculate fib(3) and fib(2) and so on.

Notice that even for a small value of 4, fib(2) is calculated twice and fib(1) is calculated thrice. This number of additions grows for large numbers.

There is a conjecture that the number of additions required for calculating fib(n) is

                     fib(n+1) -1

So this duplication is the one which is the cause of reduced performance in this particular algorithm.

The iterative algorithm for fibonacci series is considerably faster since it does not involve calculating the redundant things.

It may not be the same case for all the algorithms though.

Answer 3

If you take some recursive algorithm you can convert it to iterative by storing all function local variables in an array, effectively simulating stack on heap. If done like this there's no difference between iterative and recursive.

Note that there are (at least) two recursive Fibonacci algorithms, so for the example to be exact you need to specify which recursive algorithm you're talking about.

Answer 4

Yes, every iterative algorithm can be transformed into recursive version and vice versa. One way by passing continuations and the other by implementing stack structure. This is done without increase in time complexity.

If you can optimize tail-recursion then every iterative algorithm can be transformed to recursive one without increasing asymptotic memory complexity.

Answer 5

Yes, if you use exactly the same ideas underlying the algorithm, it does not matter. However, recursion is often easy to use with regard to iteration. For instance, writing a recursive version of the towers of Hanoi is quite easy. Transforming the recursive version into a corresponding iterative version is difficult and error prone even though it can be done. Actually there is theorem that states that every recursive algorithm can be transformed into an equivalent iterative one (doing this requires mimicking the recursion iteratively using one or more stack data structures to hold parameters passed to recursive invocations).