This week's book giveaway is in the Cloud/Virtualizaton forum.
We're giving away four copies of Mesos in Action and have Roger Ignazio on-line!
See this thread for details.
Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursion vs. iteration

 
Rachel Brunner
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am developing a web spider, using a tree structure and a hashmap. I am not sure whether to use recursion or iteration. If I use a hashmap and synchronization with recursion,will that cost a lot of time in which case it is better to do iteration?
Thank you
Rachel
 
Chinmay Bajikar
Ranch Hand
Posts: 159
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Racheal,
I think Recursion is a better option when ur using a TreeStructure.
I suppose u will have to do some work for determining how many iterations are required bforhand.
Recursion being dynamic will spare u of that work.
think u should Weigh ur options on that,
Thanks,
Chinmay
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Iteration doesn't necessarily mean you have to know the number of times a loop repeats. You could just as easily have a flag. In fact, that's what a while loop is most often used for.
However, I still agree that in general a recursion is more intuitive with a tree structure than iteration. Of course, the overhead of recursion should be taken into consideration. In the case of a web spider, I *think* iteration might be best. The best way to tell is to write a simple test application that times the two different approaches.
Also, web spiders are common enough, I'm sure Google has plenty of information about writing your own.
HTH
Layne
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, you piqued my curiosity, so I had to check out google myself. I haven't read this article, but maybe it will help you:
http://www.javacoding.net/articles/technical/java-http.html
 
Maulin Vasavada
Ranch Hand
Posts: 1873
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi all,
as a optimization part- "always try to solve a problem in iterative manner rather than recursive"...
because any lanuage has overheads of recursion like stacks and believe me i have experienced it...
once i had a program to write in ACM comptetion practice i was doing..i forgot what was the problem but i did it using recursion. one of my friend who was good at math applied some math and did the same problem iteratively.
result??
my program seemed never completing and his program came out in < 15 seconds (which was the limit we had to follow as per the program specification)...
but recursion is easy to do it i guess and can someone remind of the algos that CAN'T be achieved without recursion ?? (what are they called? i forgot) otherwise u will be able to represent each problem iteratively that can also be done using recursion.
regards
maulin
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Maulin Vasavada:
as a optimization part- "always try to solve a problem in iterative manner rather than recursive"...

On the other hand there is the first rule of (performance) optimization: Don't!
 
Maulin Vasavada
Ranch Hand
Posts: 1873
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Ilja,
i agree
but what if we 'design' the algo in iterative manner before coding it in recursion?
i miswrote that one i guess. actually i meant design+coding (and not modifying after coded).
though i agree that once sth is designed and working well to output expectations then none cares about optimization or pays little attention...
regards
maulin
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Maulin Vasavada:

but what if we 'design' the algo in iterative manner before coding it in recursion?

The initial design should almost always be optimized for maintenance (readability, extensebility) rather than performance.
Second rule of optimization (for experts only): Don't - yet
 
Michael Borgwardt
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Maulin Vasavada:
hi all,
because any lanuage has overheads of recursion like stacks and believe me i have experienced it...

The overhead is usually not the problem. The main disadvantage of recursion is that if implemented clumsily, it can easily cause the stack to overflow.

once i had a program to write in ACM comptetion practice i was doing..i forgot what was the problem but i did it using recursion. one of my friend who was good at math applied some math and did the same problem iteratively.
result??
my program seemed never completing and his program came out in < 15 seconds (which was the limit we had to follow as per the program specification)...

I suspect strongly that your recursive implementation was simply too naive, computing the same thing many times, while he reused results. A typical example are Fibonacci numbers:
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Binary/
 
John Lee
Ranch Hand
Posts: 2545
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The difference between recursion and iteration?
I think iteration process can be better characterized, but recursion can't be easily characterized, so you have to rely on process itself. If given the choice, I will take iteration, but I think recursion solution is always more graceful.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic