permaculture playing cards*
The moose likes Java in General and the fly likes Recursion vs. iteration Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Recursion vs. iteration" Watch "Recursion vs. iteration" New topic
Author

Recursion vs. iteration

Rachel Brunner
Greenhorn

Joined: Jan 16, 2003
Posts: 1
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

Joined: Dec 08, 2001
Posts: 159
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


The strength of the Wolf is the pack & the strength of the pack is the wolf....Rudyard Kipling
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
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


Java API Documentation
The Java Tutorial
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
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

Joined: Nov 04, 2001
Posts: 1871
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

Joined: Jul 11, 2001
Posts: 14112
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!


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
Maulin Vasavada
Ranch Hand

Joined: Nov 04, 2001
Posts: 1871
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

Joined: Jul 11, 2001
Posts: 14112
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

Joined: Dec 06, 2002
Posts: 9
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

Joined: Aug 05, 2001
Posts: 2545
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursion vs. iteration
 
Similar Threads
Why recursion?
Dynamically creating ArrayList inside a iterator
XML assignments released
Recursive method to print prime factorization of a number
Is my prof trolling me? (factorials, loops)