• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

Recursion vs Nested loops.

 
Ranch Hand
Posts: 419
Mac jQuery Objective C
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
lowercase baba
Posts: 12751
51
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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)
 
Ranch Hand
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Posts: 419
Mac jQuery Objective C
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks all for suggestions
 
Ranch Hand
Posts: 144
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.

 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
Marshal
Posts: 24594
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!