Recursion vs Iteration. What’s the difference between recursion and iteration.
Recursion and Iteration both are two different programming approaches. For some problems recursion is best suited and in some other cases iterative way of programming is good.
In programming, repeated set of instructions can be handled either by using recursive or iterative approach in our code. So which approach we choose and why? Let’s talk about the difference between iteration and recursion.
Difference Between Recursion and Iteration
Recursion vs Iteration – Difference Between Recursion and Iteration
i) In recursion, function call itself until the base or terminating condition is not true.
On other hand, In Iteration set of instructions repeatedly executes until the condition fails. For example – when you use loop (for, while etc.) in your code.
ii) Iterative approach involves four steps, Initialization , condition, execution and updation.
In recursive function, only base condition (terminate condition) is specified.
iii) Recursion keeps your code short and simple Whereas iterative approach makes your code longer.
iv) Recursion is slower as compared to iterative approach due to overhead of maintaining call stack.
v) Recursion takes more memory than iteration due to overhead of maintaining call stack .
vi) If recursion is not terminated (or base condition is not specified) than it creates stack overflow (where your system runs out of memory).
vii) Any recursive problem can be solved iteratively . But you can’t solve all problems using recursion.
Programming Video Tutorials on Recursion
Practice questions on recursion
Example of Programs using Recursion and Iteration Method
Let’s solved some program using both recursive and iterative approach.
Reverse a linked list using recursion
Print fibonacci series using recursion
i) Find Factorial of a Number using Recursion
|
1 2 3 4 5 6 7 8 9 10 |
int calfactorial(int n) { /* Base condition if n equals to 1 then return 1 */ if(n==1) return 1; else /* Recursive call */ return (n * calfactorial(n-1) ); } |
Factorial Program using Iterative Method
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int calfactorial (int n){ int fac = 1; for (int i = 2; i <= n; i++){ fac = fac * i; } return fac; } |
ii) Sum of N Natural Numbers using Recursion
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int sum (int n) { if ( n <= 0) { return 0; } else { /* Recursive call */ return n + sum (n-1); } } |
Sum of N Natural Numbers using Iteration
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int sum (int n) { int num = 0; for ( i = 1 ; i <= n; i++ ) { num = num + i; } return num; } |
Important Points for Recursive and Iterative Approach
1. Recursion keeps code short and clean as compared to iteration.
2. Recursion uses more memory than iteration due to overhead of call stack.
There are some problems which can be efficiently solved using recursion such as
1. Travesals (Tree, Graph search).
2. Sorting algorithms (Merge Sort, Quicksort) etc
For complex problem, it is always better to use recursion. As it reduces the code complexity and keeps code readable as compared to iteration.
Binary Search using Recursion in C
Multiply two numbers without using multiplication operator
Programming questions on recursion video tutorial
Conclusion
Never use recursion for simple programs or programs which are not recursive in nature. Iterative approach is more efficient in terms of memory utilization and speed of execution.
