Recursion vs Nested loops.

I was writing an algorithm to find unique objects in a array using Java. I have written two methods one is recursive and other is having nested loops. According to the time taken recursive is quite slow and also its takes more memory because each recursion will have a new stack allocated to the method. But in other case it was quite fast. Am I right about recursion ? If yes then what is the use of recursive functions? I read some where its easy to use and make it look simple.

I don't think you can make a blanket statement like "recursion is slower than nested loops" or "recursion uses more memory". It would depend on the algorithm in each case.

Yes, recursion does get a new call-stack on each call to itself, but that may or may not take much memory, depending on what needs to be stored. And if my recursive call only goes a few levels deep, but my nested loops require me to create hundreds of objects stored in a collection, memory usuage could be quite large.

The use of recursion is that that it is extremely powerful and some things can be written very simply using it, whereas writing it using loops or other methods leads to very complicated, confusing code.

Your goal should always be to write the cleanest, simplest code that is easy to understand than to worry about memory or speed - unless you have SPECIFIC requirements on such things.

Even then you're still better served writing simpler code first, then doing benchmarks to see what needs to be improved.

pawan chopra wrote:I was writing an algorithm to find unique objects in a array using Java. I have written two methods one is recursive and other is having nested loops. According to the time taken recursive is quite slow and also its takes more memory because each recursion will have a new stack allocated to the method. But in other case it was quite fast. Am I right about recursion ? If yes then what is the use of recursive functions? I read some where its easy to use and make it look simple.

If memory usage is the issue you can use Tail Recursion. Though it is practically not possible to change every recursive function into tail recursion but a lot depends on your requirements and implementation.

Also it will be good to share that what are you trying to do. If you are only trying to identify the unique Objects in a Collection then in both of the cases the Complexity of time will be the same. O(n)

fred rosenberger wrote:
The use of recursion is that that it is extremely powerful and some things can be written very simply using it, whereas writing it using loops or other methods leads to very complicated, confusing code.

Indeed

Thanks all for suggestions

Recursion will cause a stack overflow if it goes too deep before a base case is reached. It may be elegant, but it's not always an option.

Except if your method is tail recursive (already mentioned by Himanshu) and your compiler or JVM will optimize for this, so that a new stack frame is not needed for every recursive call. (As far as I know, Oracle's Java compiler and JVM don't perform this optimization).

However, compilers and/or VM's for functional languages do routinely optimize away tail-call recursion, because recursion is a standard technique (rather than a luxury) in a functional language.