Menu
Is there any problem that can only be solved in recursion or iteration. If not, can all algorithms be represented in either form having the same complexity?
PS: I'm talking about the theoretical complexity(O, theta and omega) and not about the time taken when implemented in real world systems.
214
Yes, any problem that can be solved recursively can also be solved through the use of iteration. In case you don't know, iteration is the use of a looping construct like a while loop, for loop, etc in order to solve a problem, whereas recursion is the use of a function that calls itself to solve a problem.
Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It is especially good for working on things that have many possible branches and are too complex for an iterative approach . One good example of this would be searching through a file system.
Recursion is a basic programming technique you can use in most of the programming languages, in which a method calls itself to solve some problem. A method that uses this technique is recursive. Some computational problems can be described in such a way that the problem can be broken down to smaller subproblems.
Iteration can be used to repeatedly execute a set of statements without the overhead of function calls and without using stack memory. Iteration is faster and more efficient than recursion. It's easier to optimize iterative codes, and they generally have polynomial time complexity.
Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion.[1]
So no, every problem that can be solved iterative can be solved with recursion and vice-versa. If you do 1:1 conversion, Big-O notation stays the same. It can, however, still be better to use an iterative algorithm over a recursive because you can do different things.
1: https://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursion_versus_iteration
72
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
