Recursion Time Complexity || Analysis of Recursion

Recursion and it’s Time Complexity

As we know ,”Recursion is a technique of repeating a set of instruction to solve a specific problem”. But How do we analyze recursion and find it’s time complexity

So, In this post we are going to discuss the method by which you can easily calculate time complexity of recursion.

Recursive Function

void fun(int n)
{
if(n<=0)
return;
fun(n/2);
fun(n/2);
}

Above Function is a recursive function and return whenever n becomes less then zero, but before returning it calls itself two time’s fun(n/2) and fun(n/2)

Suppose Time Complexity of fun(n) is be T(n)

Then Time complexity of fun(n/2) is T(n/2) [Simple Mathematics]

So we can say T(n) = T(n/2) + T(n/2) + C [Above Recursive Function]

Where C is constant and represents time complexity of the given code from an above recursive function

if(n<=0)
return

Now, we know how to write the equation and the only part remained is to calculate time complexity. So here are two simple step

  1. We write non-recursive part as the root of a tree and recursive part as children
  2. We keep expanding until we see a pattern
                       From T(n) = 2T(n/2) + C

Recursive Part = 2T(n/2)
Non Recursive Part = C
               Follow Step - 1

1.                             C  [Non-Recursive Part as the root of a tree]
                           /       \
                         T(n/2)     T(n/2)      [Recursive Part as Children]

Now, we know how to write Root and Children, Now we are going to create up to 4 levels so we can see a pattern easily

                    Level 1   C
                          /    \
             Level 2   T(n/2)  T(n/2)    

But we know T(n/2) = 2T(n/4) + C---(2)   [Replace n by n/2 in equation 1]
Again we follow step 1
        Level 1          C    from eq(1) [Non Recursive Part as Root]
                     /      \
      Level 2      C          C     from eq (2)[Non Recursive Part as Root]
                /   \        /  \
  Level 3    T(n/4) T(n/4)T(n/4) T(n/4)    [Recursive Part as children]

But we again Know T(n/4) = 2T(n/8) + C---(3)[Replace n by n/4 in equation 1]

       Level 1          C    from eq(1) [Non Recursive Part as Root]
                     /      \
      Level 2     C          C     from eq (2)[Non Recursive Part as Root]
                /   \        /  \
    Level 3    C     C      C    C from eq (3) [Non Recursive part as root]
             /   \  /   \  /  \ / \ 
Lev 4 T(n/8)T(n/8)T(n/8)T(n/8)T(n/8)T(n/8)T(n/8)T(n/8)[Recursive part as children]


Now add Constant time at every level and you will see a pattern

Level – 1 C

Next Level – 2 2C

Next Level – 3 4C

And you may guess that at level 4 Sum must be 8C

Hence add time at each level T(n) = C+ 2C + 4C + 8C +………

Now, we are able to find the equation, but can you guess what is the number of terms in this series.

Yes, Every time n becomes n/2 so total number of terms should be log(n)

So add the above series with n = log(n) and r = 2 and add above Geometric Progression

T(n) = (1 * (2^log(n) – 1)) / (2-1) [Formula of sum of GP]

T(n) = 2^log(n) – 1

O(T(n)) = 2^log(n)

Hence we are able to know the time complexity of Above recursive function

Calculate Time complexity of below recursive function

T(n) = 2T(n/2) + Cn

T(n) = T(n) + Cn;

Tagged : / /

Recursion | The Art of Repetition

What is Recursion?

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Certain problems can be solved quite easily Using a recursive algorithm, Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, Binary Search etc.

What is base condition in recursion?

The solution to the base case is provided in the recursive program and the solution of the bigger problem is expressed in terms of smaller problems

int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}

In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached.

Solving Problem using recursion?.

The idea is to represent a problem in terms of one or smaller problems, and add one or more base conditions that stop the recursion. For example, we compute factorial n if we know factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.

Why Stack Overflow error occurs?

Stack overflow problem may arise If base case is not reached. Let us take an example to understand this.

int fact(int n)
{
    // wrong base case (it may cause
    // stack overflow).
    if (n == 100) 
        return 1;

    else
        return n*fact(n-1);
}

If fact(10) is called, it will call fact(9), fact(8), fact(7) and so on but number will never reach 100. So, the base case is not reached. Stack overflow error occur If the memory is exhausted by these functions on the stack, it will cause

Allocation of memory in recursion

When any function is called from main(), the memory is allocated to it on stack. A recursive function calls itself, the memory for called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.

Let us take the example how recursion works by taking a simple function

void printFun(int test)
{
    if (test < 1)
        return;
    else
    {
        print test;
        printFun(test-1);    // statement 2
        print test;
        return;
    }
}

// Calling function printFun()
int test = 3;
printFun(test);

Output :

3 2 1 1 2 3

When printFun(3) is called from main(), memory is allocated to printFun(3) and a local variable test is initialized to 3 and statement 1 to 4 are pushed on the stack as shown in below diagram. It first prints ‘3’. In statement 2, printFun(2) is called and memory is allocated to printFun(2) and a local variable test is initialized to 2 and statement 1 to 4 are pushed in the stack. Similarly, printFun(2) calls printFun(1) and printFun(1) calls printFun(0). printFun(0) goes to if statement and it return to printFun(1). Remaining statements of printFun(1) are executed and it returns to printFun(2) and so on. In the output, value from 3 to 1 are printed and then 1 to 3 are printed. The memory stack has been shown in below diagram.

When printFun(3) is called from main(), memory is allocated to printFun(3) and a local variable test is initialized to 3 and statement 1 to 4 are pushed on the stack as shown in below diagram. It first prints ‘3’. In statement 2, printFun(2) is called and memory is allocated to printFun(2) and a local variable test is initialized to 2 and statement 1 to 4 are pushed in the st

recursion

Disadvantage / Advantage

Note that both recursive and iterative programs have same problem solving powers, i.e., every recursive program can be written iteratively and vice versa is also true. Recursive program will remain in stack until base case is reached hence has greater space requirements than iterative program as all functions . It also has greater time requirements because of function calls and return overhead.

Recursion provides a clean and simple way to write code. Some problems are inherently recursive like tree traversals, Tower of Hanoi, etc. Recursive case is preferred for this type of problem We can write such codes also iteratively with the help of the stack data structure.

Tagged : / /