File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes Recursion vs Nested loops. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Recursion vs Nested loops." Watch "Recursion vs Nested loops." New topic
Author

Recursion vs Nested loops.

pawan chopra
Ranch Hand

Joined: Jan 23, 2008
Posts: 413

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.


Pawan Chopra
SCJP - DuMmIeS mInD
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11475
    
  16

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

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)

My Blog SCJP 5 SCWCD 5
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

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
pawan chopra
Ranch Hand

Joined: Jan 23, 2008
Posts: 413

Thanks all for suggestions
Mike Isano
Ranch Hand

Joined: Jan 19, 2007
Posts: 144

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.

Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14338
    
  22

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).


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18879
    
    8

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursion vs Nested loops.