Menu
I am trying to do work with examples on Trees as given here: http://cslibrary.stanford.edu/110/BinaryTrees.html These examples all solve problems via recursion, I wonder if we can provide a iterative solution for each one of them, meaning, can we always be sure that a problem which can be solved by recursion will also have a iterative solution, in general. If not, what example can we give to show a problem which can be solved only by recursion/Iteration?
--
303
Recursion has more expressive power than iterative looping constructs. I say this because a while loop is equivalent to a tail recursive function and recursive functions need not be tail recursive. Powerful constructs are usually a bad thing because they allow you to do things that are difficult to read.
The main difference between recursion and loop is that recursion is a mechanism to call a function within the same function while loop is a control structure that helps to execute a set of instructions again and again until the given condition is true. Recursion and loop are two programming concepts.
Using recursion in the divide and conquer method can minimize the size of your problem at each step and take less time than a naive iterative approach. It is frequently more 'elegant' to use recursion than iterative solutions because it is easier to implement.
In general, no, recursion will not be faster than a loop in any realistic usage that has viable implementations in both forms. I mean, sure, you could code up loops that take forever, but there would be better ways to implement the same loop that could outperform any implementation of the same problem via recursion.
The only difference between iteration and recursion on a computer is whether you use the built-in stack or a user-defined stack. So they are equivalent.
76
In my experience, most recursive solution can indeed be solved iteratively.
It is also a good technique to have, as recursive solutions may have too large an overhead in memory and CPU consumptions.
31
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
