• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursion vs Nested loops.

 
pawan chopra
Ranch Hand
Posts: 417
jQuery Mac 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.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12186
34
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.
 
Himanshu Gupta
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)
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Java Windows XP
  • 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: 417
jQuery Mac Objective C
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks all for suggestions
 
Mike Isano
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.

 
Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15451
42
Android IntelliJ IDE Java Scala Spring
  • 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).
 
Paul Clapham
Sheriff
Posts: 21322
32
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic