Performance comparison between Recursive Algorithm and Non-Recursive Algorithm
Recursive Algorithm is comparatively slower because before each function call the current state of function is stored in stack. After the return statement the previous function state is again restored from stack. Non-Recursive Algorithms execution is faster because it doesn’t use stack
Also, Memory usage is more in Recursive Algorithm as stack is used to store the current function state. Memory usage is less in Non-Recursive Algorithm as it doesn’t use stack.
These two kinds of algorithms can be compared furthermore based on following facts,
Time Complexity
Finding the Time complexity of Recursive is more difficult than that of Non-Recursive
- Recursive Algorithm
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.
- Non-Recursive Algorithm
Time complexity Non-Recursive Algorithms can be found by finding the number of cycles being repeated inside the loop.
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 number of recursive calls would be large, it is better to use Non-Recursive Algorithm. However, if time complexity is not an issue and shortness of code is, recursion would be the way to go.
- Recursive Algorithm
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.
- Non-Recursive Algorithm
Non-Recursive Algorithm is 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
Overhead
Recursion has a large amount of Overhead as compared to Non-Recursive Algorithm.
- Recursive Algorithm
Recursion has the overhead of repeated function calls, that is due to repetitive calling of the same function, the time complexity of the code increases manifold.
- Non-Recursive Algorithm
Non-Recursive Algorithm does not involve any such overhead.
Infinite Repetition
Infinite Repetition in recursion can lead to CPU crash but in Non-Recursive Algorithm, it will stop when memory is exhausted.
- Recursive Algorithm
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 system CPU crash.
- Non-Recursive Algorithm
Infinite Non-Recursive Algorithm due to mistake in Non-Recursive Algorithm 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.
So these facts sums up the performance between recursive and non-recursive algorithms. cheers!!
