The set of instructions is repeated using both recursion and iteration. When a statement within a function repeatedly invokes itself, recursion occurs. Iteration happens when a loop runs repeatedly until the controlling condition is satisfied. Recursion and iteration vary fundamentally doing the same thing. iteration is used to apply a set of instructions that we want to perform again, whereas recursion is a procedure always applied to a function.
Learn more about recursion and iteration, as well as how they differ from one another, by reading this article.
Recursion Vs Iteration: Comparative Analysis
The Fibonacci numbers are an integer sequence with the first two elements being 0 and 1, and each succeeding element being the sum of the two items before it:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …, n
Recursion
Code of Fibonacci number in a recursive way
public static int fibonacciRecursion(int nthNumber) {
//use recursion
if (nthNumber == 0) {
return 0;
} else if (nthNumber == 1) {
return 1;
}
return fibonacciRecursion(nthNumber - 1) + fibonacciRecursion(nthNumber - 2);
}
Analysis
The result is a neatly constructed function that checks. We return both the given numbers if the given number is equal to either 0 or 1.
If a number is passed that is bigger than 0 and 1, we perform two recursive calls, adding both calls and subtracting 1 and 2 from the nthNumber in each call.
We will most likely quickly receive –> 0, 1, 1, 2, 3, if we pass these integers (0, 1, 2, 3, 4, and 5).
However, what occurs if we pass greater numbers, such as 50, 67, or 100. In your IDE, try running the function with the supplied numbers. You’ll realize that this method takes much longer to calculate our Fibonacci number. Due to the fact that this recursive function has many internal workings because it does repeated computation and this issue we will solve by memorizing the value. Heavy push-pop operations on the stack memory with each recursive call are to blame for the performance issues.
A workaround for this would be to memorize and keep each Fibonacci number that has been calculated in this way. However, I’ll move on to the Iteration approach for now and explain why it might speed up the computation of the 100th Fibonacci number.
Iteration
Code of Fibonacci number in an iterative way
public static int fibonacciLoop(int nthNumber) {
//use loop
int previouspreviousNumber, previousNumber = 0, currentNumber = 1;
for (int i = 1; i < nthNumber ; i++) {
previouspreviousNumber = previousNumber;
previousNumber = currentNumber;
currentNumber = previouspreviousNumber + previousNumber;
}
return currentNumber;
}
Analysis
Because we are keeping the first two Fibonacci numbers in two variables (previousPreviousNumber, previousNumber) and utilizing “CurrentNumber” to store the third Fibonacci number, the Iteration method would be the preferred and faster approach to solving our problem. By storing these values, we can avoid continuously eating up Stack RAM. giving us an O(n) time complexity.
Comparative Analysis
- Time ComplexityDepending on whether the technique is applied via recursion or iteration, the method’s time complexity may change.Recursion: By calculating the value of the nth recursive call in terms of the prior calls, the time complexity of the recursion can be determined. We may therefore estimate the time complexity of recursive equations by determining the destination case in terms of the base case and solving in terms of the base case.Iteration: Finding the number of cycles repeated inside the loop will reveal the iteration’s time complexity.
- UsageBoth of these methods involve a trade-off between time complexity and code size. Iteration is preferable if time complexity is the main concern and there will be a lot of recursive calls. However, recursion would be the best option if time complexity was not a concern and code length was.Recursion: Recursion includes repeatedly calling the same function, which results in relatively little code. However, as we saw in the study, when there are a lot of recursive calls, the time complexity of recursion might become exponential. Recursion is, therefore, helpful in shorter code but more time-consuming.Iteration: The repetition of a block of code is known as iteration. Although there is more code involved, it often takes less time than recursion does.
- OverheadCompared to iteration, recursion has a lot more overhead.Recursion: Recursion has the overhead of repeated function calls, which means that because the same function is called repeatedly, the code’s time complexity multiplies.Iteration: There is no such overhead with iteration.
- Infinite RepetitionIn iteration, repetition will end when memory is used up. However, infinite repetition in recursion can cause a CPU crash.Recursion: Recursion can result in infinite recursive calls if the base condition is specified incorrectly and never becomes false, which keeps calling the function and could cause the system’s CPU to crash.Iteration: An infinite iteration caused by an error in the assignment or increment of the iterator or in the terminating condition will result in infinite loops. These loops may or may not cause system faults, but they will definitely stop further script execution.
Difference between Recursion and Iteration
The key differences between iteration and recursion are listed in the table below:
| Property | Recursion | Iteration |
|---|---|---|
| TextDefinition | The function invokes itself. | A series of instructions that are repeated. |
| Application | For functions. | For loops. |
| Termination | Base scenario, in which there won’t be a function call. | When the termination condition for the iterator ceases to be satisfied. |
| Usage | Used when a compact code base is required and time complexity is unimportant. | Used when the trade-off between increased code size and time complexity needs to be considered. |
| Code Size | Smaller code size | Larger Code Size. |
| Time Complexity | Exceptionally high time complexity (often exponential). | Relatively less complex in terms of time (often polynomial-logarithmic). |
| Space Complexity | The space complexity is higher than iterations. | Space complexity is lower. |
| Stack | When the function is invoked in this case, local variables are stored on the stack. | Stack is not used. |
| Speed | Since a cost is associated with maintaining and updating the stack, execution is delayed. | Since it doesn’t use the stack, it typically runs faster than recursion. |
| Memory | In comparison to iteration, recursion consumes more memory. | Recursion consumes more memory than iteration. |
| Overhead | Possesses overhead of repeated function calls. | No overhead because iteration doesn’t involve calling any functions. |
| Infinite Repetition | There is a potential that a system could crash under infinite recursion if the recursive function does not satisfy a termination condition, the base case is not defined, or it is never reached. | An infinite loop will result if the control condition of the iteration statement never becomes false or the control variable does not reach the termination value. It repeatedly uses CPU cycles while in the infinite loop. |
FAQs
Q. Which consumes more memory: recursion or iteration?
A. Because of the expense associated with maintaining the stack, recursion is typically slower than iteration. Iteration utilizes less memory than recursion.
Q. Does iteration take longer than recursion?
A. Although the theoretical time complexity of the two programs is equal, the execution time of the recursive program will be longer due to the overhead of function calls, which is significantly larger than that of iteration.
Q. Is recursion simpler to use than iteration?
A. Recursive solutions are typically easier to develop and, therefore, more ‘elegant’ than iterative ones. Therefore, we advise choosing a strategy that seems logical, is not overly complicated, and communicates your thought process.
Q. Can recursion address issues that iteration cannot?
A. So no, recursion and iteration may be used to solve any problem, and vice versa. Big-O notation remains unchanged if you convert at a 1:1 rate. However, as an iterative approach allows for more flexibility than a recursive one, it may still be preferable.
Conclusion
- In conclusion, recursion and iteration are distinct approaches in programming.
- Recursion relies on function calls that build upon each other, making it suitable for problems with a recursive structure but potentially consuming more memory.
- Iteration, on the other hand, employs loops to repeatedly execute code, offering a more memory-efficient and straightforward solution for many problems.
- The choice between recursion and iteration depends on the problem’s nature, readability, and efficiency considerations. Programmers should select the appropriate technique based on these factors to effectively solve programming challenges.
I hope you liked this article.
