Header Ads Widget

Iteration and Recursion

Recursion

Recursion is said to be the process of repeating things in a similar manner. In computer science, recursion is a process of calling a function itself within its own code. Any function which calls itself is called a recursive function, and such function calls are called recursive calls.

During defining the recursion, one must define an exit condition carefully; otherwise, it will go to an infinite loop. So, it is important to impose a termination condition of recursion. It is slower than iteration because of the overhead of maintaining of the stack. Recursion code is shorter than iterative code; however, it is difficult to understand. Recursive functions are helpful in solving various problems such as finding the factorial of a number, creating the Fibonacci series, etc.

Let's see an example of finding the factorial of a number using recursion.

C program to find the factorial of a number using recursion

#include <stdio.h>    
int fact(int n)    
{    
    if (n == 0)    
        return 1;    
    else     
        return n * fact(n-1);    
}   
  
int main()    
{    
    int n,f;    
    printf("Enter any number: ");    
    scanf("%d", &n);    
    f = fact(n);    
    printf("factorial = %d",f);    

Output

Recursion vs Iteration

Iteration

In Iteration, there is the usage of loops to execute the set of instructions repetitively until the condition of the iteration statement becomes false. It is comparatively faster than recursion. It has a larger code size than recursion. The termination in iteration happens when the condition of the loop fails.

In iteration, the time complexity is relatively lower than recursion. We can calculate its time complexity by finding the no. of cycles being repeated in a loop.

Now, let's see the program to find the factorial of a number using iteration.

C program to find the factorial of a number using iteration

#include <stdio.h>    
int fact(int num)    
{    
   int res = 1, i;  
    
    for (i = 2; i <= num; i++)  
        res *= i;  
    return res;  
}   
  
int main()    
{    
    int num, f;    
    printf("Enter any number: ");    
    scanf("%d", &num);    
    f = fact(num);    
    printf("factorial = %d", f);    
}

Output

Recursion vs Iteration

Recursion v/s Iteration

Now, let's see the comparison between iteration and recursion. We are comparing both terms based on some characteristics.

On the basis of

Recursion

Iteration

Basic

Recursion is the process of calling a function itself within its own code.

In iteration, there is a repeated execution of the set of instructions. In Iteration, loops are used to execute the set of instructions repetitively until the condition is false.

Syntax

There is a termination condition is specified.

The format of iteration includes initialization, condition, and increment/decrement of a variable.

Termination

The termination condition is defined within the recursive function.

Here, the termination condition is defined in the definition of the loop.

Code size

The code size in recursion is smaller than the code size in iteration.

The code size in iteration is larger than the code size in recursion.

Infinite

If the recursive function does not meet to a termination condition, it leads to an infinite recursion. There is a chance of system crash in infinite recursion.

Iteration will be infinite, if the control condition of the iteration statement never becomes false. On infinite loop, it repeatedly used CPU cycles.

Applied

It is always applied to functions.

It is applied to loops.

Speed

It is slower than iteration.

It is faster than recursion.

Usage

Recursion is generally used where there is no issue of time complexity, and code size requires being small.

It is used when we have to balance the time complexity against a large code size.

Time complexity

It has high time complexity.

The time complexity in iteration is relatively lower. We can calculate its time complexity by finding the no. of cycles being repeated in a loop.

Stack

It has to update and maintain the stack.

There is no utilization of stack.

Memory

It uses more memory as compared to iteration.

It uses less memory as compared to recursion.

Overhead

There is an extensive overhead due to updating and maintaining the stack.

There is no overhead in iteration.


Post a Comment

0 Comments