Difference Between Recursion and Iteration

Key Difference – Recursion vs Iteration
 

Recursion and Iteration can be used to solve programming problems. The approach to solving the problem using recursion or iteration depends on the way to solve the problem. The key difference between recursion and iteration is that recursion is a mechanism to call a function within the same function while iteration is to execute a set of instructions repeatedly until the given condition is true. Recursion and Iteration are major techniques for developing algorithms and building software applications.

CONTENTS

1. Overview and Key Difference
2. What is Recursion
3. What is Iteration
4. Similarities Between Recursion and Iteration
5. Side by Side Comparison – Recursion vs Iteration in Tabular Form
6. Summary

What is Recursion?

When a function calls itself within the function, it is known as Recursion. There are two types of recursion. They are finite recursion and infinite recursion. Finite recursion has a terminating condition. Infinite recursion does not have a terminating condition.

Recursion can be explained using the program to calculate factorials.

n! = n * (n-1)!, if n>0

n! =1 ,if n=0;

Refer the bellow code to calculate factorial of 3(3!= 3*2*1).

intmain () {

int value =factorial (3);

printf(“Factorial is %d\n”, value);

return 0;

}

intfactorial (intn) {

if(n==0) {

return 1;

}

else {

return n* factorial(n-1);

}

}

When calling factorial (3), that function will call factorial (2). When calling factorial (2), that function will call factorial (1). Then factorial (1) will call factorial (0). factorial (0) will return 1. In the above program, n==0 condition in the “if block” is the base condition. According to the Likewise, the factorial function is called again and again.

Recursive functions are related with the stack. In C, the main program can have many functions. So, main () is the calling function, and the function which is called by the main program is the called function. When the function is called, the control is given to the called function. After the function execution is completed, the control is returned to main. Then the main program continues. So, it creates an activation record or a stack frame to continue execution.

In the above program, when calling factorial (3) from main, it creates an activation record in the call stack. Then, factorial (2) stack frame is created on top of the stack and so on. The activation record keeps information about local variables etc. Each time the function is called, a new set of local variables are created on the top of the stack. These stack frames can slow down the speed up. Likewise in recursion, a function calls itself. Time complexity for a recursive function is found by the number of times, the function is called.  Time complexity for one function call is O(1). For n number of recursive calls, the time complexity is O(n).

What is Iteration?

Iteration is a block of instructions which repeats again and again till the given condition is true. Iteration can be achieved using “for loop”, “do-while loop” or “while loop”. “for loop” syntax is as follows.

for (initialization; condition; modify) {

// statements;

}

Initialization step executes first. This step is to declare and initialize loop control variables. If the condition is true, the statements inside the curly braces execute. Those statements execute till the condition is true. If the condition is false, the control goes to the next statement after the “for loop”. After executing the statements inside the loop, the control goes to modify section. It is to update the loop control variable. Then the condition is checked again. If the condition is true, the statements inside the curly braces will execute. This way the “for loop” iterates.

In “while loop”, the statements inside the loop executes until the condition is true.

while (condition){

//statements

}

In “do-while” loop, the condition is checked at the end of the loop. So, the loop executes at least once.

do{

//statements

} while(condition)

Program to find the factorial of 3 (3!) using iteration (“for loop”) is as follows.

int main(){

intn=3, factorial=1;

inti;

for(i=1; i<=n ; i++){

factorial = factorial *  i;

}

printf(“Factorial is %d\n”, factorial);

return 0;

}

What are the Similarities Between Recursion and Iteration?

• Both are techniques to solve a problem.
• The task can be solved either in recursion or iteration.

What is the Difference Between Recursion and Iteration?

Summary – Recursion vs Iteration

This article discussed the difference between recursion and iteration. Both can be used to solve programming problems. The difference between recursion and iteration is that recursion is a mechanism to call a function within the same function and iteration it to execute a set of instructions repeatedly until the given condition is true. If a problem can be solved in recursive form, it can also be solved using iterations.

Download the PDF Version of Recursion vs Iteration

You can download PDF version of this article and use it for offline purposes as per citation note. Please download PDF version here Difference Between Recursion and Iteration

Reference:

1.Point, Tutorials. “Data Structures and Algorithms Recursion Basics.”, Tutorials Point, 15 Aug. 2017. Available here 
2.nareshtechnologies. “Recursion in C Functions | C Language Tutorial”YouTube, YouTube, 12 Sept. 2016.  Available here  
3.yusuf shakeel. “Recursion Algorithm | Factorial – step by step guide”YouTube, YouTube, 14 Oct. 2013.  Available here  

Image Courtesy:

1.’CPT-Recursion-Factorial-Code’By Pluke – Own work, (Public Domain) via Commons Wikimedia 
2.’For-loop-diagram’By No machine readable author provided – Own work assumed. (CC BY-SA 2.5) via Commons Wikimedia