Practically understanding time complexities of Recursive and Iterative functions

We will consider the Fibonacci function to compare the time complexities of the Recursive and Iterative function.

Photo by Aron Visuals on Unsplash

Basic Definitions

1. Recursion: The process in which the function keeps calling itself directly or indirectly.
2. Iteration: The process in which certain set of instructions are executed repeatedly.

Algorithms for Recursive and Iterative Fibonacci calculation

1. Recursive

recursivefib(n):
   if n <2
       return n
   return recursivefib(n - 1) + recursivefib(n - 2)

2. Iterative

iterativefib(n):
    x=0, y=1
    if n<2
        return n
    for (i=2; i<=n; i++)
   {
      z=x+y
      x=y
      y=z
   }
   return y

As it is observed in the algorithm, Recursive function keeps calling itself till a base condition (i.e n<2) is reached. While the iterative function uses for loop to repeatedly execute a set of instructions (in this case: z=x+y; x=y; y=z;).

In the recursive algorithm the if statement takes constant time but the time taken by the recursive statement (recursivefib(n — 1) + recursivefib(n — 2) ) depends on the input. Recursive calls make use of the stack, so the larger the input more the number of stacks are required.

In the iterative algorithm the if statement takes constant time but the time taken by the for loop depends on the input. The statements inside the for loop (in this case) takes a constant amount of time. So those statements will be repeatedly executed according to the input.

So now let’s see how much time does iterative and recursive function takes in reality. To do this I have used the built-in Java function to calculate the time taken by both functions.

Java code for calculating time required by recursive and iterative functions:

import java.util.Scanner;

public class Fibonacci {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.print("Enter N: ");
        int n = sc.nextInt();
        sc.close(); 

        if(n<0)
        {
        	System.out.println("No Negative Numbers allowed");
        	return;
        }
        
        long time;

        System.out.println("Iterative Function:");
        time = System.currentTimeMillis();
        System.out.printf("Sequence Number at index %d = %d \n", n, iterativefib(n));
        System.out.printf("Time using Iteration: %d ms\n", System.currentTimeMillis() - time);
        
        System.out.println("Recursive Function:");
        time = System.currentTimeMillis();
        System.out.printf("Sequence Number at index %d = %d \n", n, recursivefib(n));
        System.out.printf("Time using Recursion: %d ms\n", System.currentTimeMillis() - time);
    }


    static long recursivefib(int  n) {
        if (n<2) 
            return n;
        return recursivefib(n - 1) + recursivefib(n - 2);
    }
    
    static long iterativefib(int n) {
        long f1 = 0, f2 = 1, f3;
        if(n<2)
        	return n;
        for (int i = 2; i <=n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f2;
    }
}

Now lets see what output we get with increasing input size:

Note: the time we got in the output depends on many factors like the number of processes running in your system other than just the function itself. so when you run the code at your end the output may be a bit different but the behavior of the function will be the same. Also in the above code, the time to print the output is included, so you can modify the code accordingly if you want to exclude printing time.

Now we have the real scenario of the time requirements by recursive and iterative functions. So let us discuss briefly on time complexity and the behavior of Recursive v/s Iterative functions.

• Finding the time complexity of Recursion is more complex than that of Iteration.
• As mentioned above, Recursion calls the same function again and again which leads to a large overhead as each recursive call requires its(own) stack.
• Whereas Iteration is just the repetition of the same block of code which makes the code size larger but doesn’t have large overheads as compared to recursion.
• In the case of recursion, we can calculate the time complexity by the use of a recursive tree which is generated by recursive calls. The recurrence equation of recursive tree is given as T(n) = T(n-1) + T(n-2) + c
• On solving the above recurrence equation, we get the time complexity is O(2^n).
• The above-mentioned time complexity is exponential which is evident from the values shown in the output corresponding to Input N. With increasing values of N, the time required to calculate the Nth Fibonacci number using recursion is also increasing exponentially.
• In the case of iteration, it is first observed that the time required is more than the recursive Fibonacci function for smaller values of N, but as the values of N increase and after a certain value of N the time required by iterative Fibonacci function is always less than recursive one.
• The exponential behavior seen in recursion is due to the nested calls and their corresponding stack overhead.

For any technical or other errors, feel free to contact me so that further readers are benefitted.

Thank You for reading. Knowledge is power, so keep gaining!😈

Follow me on GitHub!