A program is called recursive when an entity calls itself. A program is called iterative when there is a loop (or repetition).
Example: Program to find the factorial of a number
C
// C program to find factorial of given number#include <stdio.h>// ----- Recursion -----// method to find factorial of given numberint factorialUsingRecursion(int n){ if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1);}// ----- Iteration -----// Method to find the factorial of a given numberint factorialUsingIteration(int n){ int res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res;}// Driver methodint main(){ int num = 5; printf("Factorial of %d using Recursion is: %d\n", num, factorialUsingRecursion(5)); printf("Factorial of %d using Iteration is: %d", num, factorialUsingIteration(5)); return 0;}// This code is contributed by mits |
C++
// C++ program to find factorial of given number#include<bits/stdc++.h>using namespace std;// ----- Recursion -----// method to find factorial of given numberint factorialUsingRecursion(int n){ if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1);}// ----- Iteration -----// Method to find the factorial of a given numberint factorialUsingIteration(int n){ int res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res;}// Driver methodint main(){ int num = 5; cout << "Factorial of " << num << " using Recursion is: " << factorialUsingRecursion(5) << endl; cout << "Factorial of " << num << " using Iteration is: " << factorialUsingIteration(5); return 0;}// This code is contributed by mits |
Java
// Java program to find factorial of given numberclass GFG { // ----- Recursion ----- // method to find factorial of given number static int factorialUsingRecursion(int n) { if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1); } // ----- Iteration ----- // Method to find the factorial of a given number static int factorialUsingIteration(int n) { int res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res; } // Driver method public static void main(String[] args) { int num = 5; System.out.println("Factorial of " + num + " using Recursion is: " + factorialUsingRecursion(5)); System.out.println("Factorial of " + num + " using Iteration is: " + factorialUsingIteration(5)); }} |
Python3
# Python3 program to find factorial of given number# ----- Recursion -----# method to find factorial of given numberdef factorialUsingRecursion(n): if (n == 0): return 1; # recursion call return n * factorialUsingRecursion(n - 1);# ----- Iteration -----# Method to find the factorial of a given numberdef factorialUsingIteration(n): res = 1; # using iteration for i in range(2, n + 1): res *= i; return res;# Driver methodnum = 5;print("Factorial of",num,"using Recursion is:", factorialUsingRecursion(5));print("Factorial of",num,"using Iteration is:", factorialUsingIteration(5)); # This code is contributed by mits |
C#
// C# program to find factorial of // given numberusing System;class GFG{ // ----- Recursion ----- // method to find factorial of // given number static int factorialUsingRecursion(int n) { if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1); } // ----- Iteration ----- // Method to find the factorial of // a given number static int factorialUsingIteration(int n) { int res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res; } // Driver Code public static void Main(String[] args) { int num = 5; Console.WriteLine("Factorial of " + num + " using Recursion is: " + factorialUsingRecursion(5)); Console.WriteLine("Factorial of " + num + " using Iteration is: " + factorialUsingIteration(5)); }}// This code has been contributed by Rajput-Ji |
PHP
<?php// PHP program to find factorial of given number // ----- Recursion ----- // method to find factorial of given number function factorialUsingRecursion($n) { if ($n == 0) return 1; // recursion call return $n * factorialUsingRecursion($n - 1); } // ----- Iteration ----- // Method to find the factorial of a given number function factorialUsingIteration($n) { $res = 1; // using iteration for ($i = 2; $i <= $n; $i++) $res *= $i; return $res; } // Driver method $num = 5; print("Factorial of ".$num." using Recursion is: ". factorialUsingRecursion(5)."\n"); print("Factorial of ".$num." using Iteration is: ". factorialUsingIteration(5)."\n"); // This code is contributed by mits?> |
Javascript
<script>// JavaScript program to find factorial of given number// ----- Recursion -----// method to find factorial of given numberfunction factorialUsingRecursion(n) { if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1); } // ----- Iteration ----- // Method to find the factorial of a given number function factorialUsingIteration(n) { var res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res; } // Driver method var num = 5; document.write("Factorial of " + num + " using Recursion is: " + factorialUsingRecursion(5)+"<br>"); document.write("Factorial of " + num + " using Iteration is: " + factorialUsingIteration(5)); // This code is contributed by shivanisinghss2110</script> |
Output
Factorial of 5 using Recursion is: 120 Factorial of 5 using Iteration is: 120
Time and Space Complexity
Time Complexity: O(2n) Auxiliary Space: O(n)
Below is a detailed explanation to illustrate the difference between the two using the above example. We will study the different aspects of both recursive and iterative approaches.
1. Time Complexity
The time complexity of the method may vary depending on whether the algorithm is implemented using recursion or iteration.
- Recursion: The time complexity of recursion can be found by finding the value of the nth recursive call in terms of the previous calls. Thus, finding the destination case in terms of the base case, and solving in terms of the base case gives us an idea of the time complexity of recursive equations. Please see Solving Recurrences for more details.
- Iteration: The time complexity of iteration can be found by finding the number of cycles being repeated inside the loop.
2. Usage
Usage of either of these techniques is a trade-off between time complexity and size of code. If time complexity is the point of focus, and the number of recursive calls would be large, it is better to use iteration. However, if time complexity is not an issue and shortness of code is, recursion would be the way to go.
- Recursion: Recursion involves calling the same function again, and hence, has a very small length of code. However, as we saw in the analysis, the time complexity of recursion can get to be exponential when there are a considerable number of recursive calls. Hence, usage of recursion is advantageous in shorter code, but higher time complexity.
- Iteration: Iteration is the repetition of a block of code. This involves a larger size of code, but the time complexity is generally lesser than it is for recursion.
3. Overhead
Recursion has a large amount of Overhead as compared to Iteration.
- Recursion: Recursion has the overhead of repeated function calls, that is due to the repetitive calling of the same function, the time complexity of the code increases manyfold.
- Iteration: Iteration does not involve any such overhead.
4. Infinite Repetition
Infinite Repetition in recursion can lead to a CPU crash but in iteration, it will stop when memory is exhausted.
- Recursion: In Recursion, Infinite recursive calls may occur due to some mistake in specifying the base condition, which on never becoming false, keeps calling the function, which may lead to a system CPU crash.
- Iteration: Infinite iteration due to a mistake in iterator assignment or increment, or in the terminating condition, will lead to infinite loops, which may or may not lead to system errors, but will surely stop program execution any further.
Difference between Iteration and Recursion
The following table lists the major differences between iteration and recursion:
|
Property |
Recursion |
Iteration |
|---|---|---|
| Definition | Function calls itself. | A set of instructions repeatedly executed. |
| Application | For functions. | For loops. |
| Termination | Through base case, where there will be no function call. | When the termination condition for the iterator ceases to be satisfied. |
| Usage | Used when code size needs to be small, and time complexity is not an issue. | Used when time complexity needs to be balanced against an expanded code size. |
| Code Size | Smaller code size | Larger Code Size. |
| Time Complexity | Very high(generally exponential) time complexity. | Relatively lower time complexity(generally polynomial-logarithmic). |
| Space Complexity | The space complexity is higher than iterations. | Space complexity is lower. |
| Stack | Here the stack is used to store local variables when the function is called. | Stack is not used. |
| Speed | Execution is slow since it has the overhead of maintaining and updating the stack. | Normally, it is faster than recursion as it doesn’t utilize the stack. |
| Memory | Recursion uses more memory as compared to iteration. | Iteration uses less memory as compared to recursion. |
| Overhead | Possesses overhead of repeated function calls. | No overhead as there are no function calls in iteration. |
| Infinite Repetition | If the recursive function does not meet to a termination condition or the base case is not defined or is never reached then it leads to a stack overflow error and there is a chance that the an system may crash in infinite recursion. | If the control condition of the iteration statement never becomes false or the control variable does not reach the termination value, then it will cause infinite loop. On the infinite loop, it uses the CPU cycles again and again. |
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
