# Recursion vs. iteration

Rachel Brunner
Greenhorn
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
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

Layne Lund
Ranch Hand
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

Layne Lund
Ranch Hand
Posts: 3061
http://www.javacoding.net/articles/technical/java-http.html

Ranch Hand
Posts: 1873
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
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!

Ranch Hand
Posts: 1873
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

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