Hi all,

can any one give a example program where recursive version is faster
than iterative version ?

aarklon@gmail.com wrote:

For trivial programs there may or may not be examples where recursion is
faster.

But recursion is a natural fit for many kinds of programming which would be
a pain to implement with iterative methods.

Especially with making arrangements to save/restore complex data which may
well end up slower than just using recursion. But even if recursion was
slower, the difference would be minimal in a real application, while keeping
the code much cleaner.

Bartc said:

There is, however, no shortage of examples where recursion is /slower/.

Right. We don't recurse for speed, but for clarity (where it /is/ clearer)
- and even then only if the cost in terms of speed loss is more than
adequately compensated by the gain in clarity.

To take a famous example, the following code:

On Mon, 2 Jun 2008 03:29:17 -0700 (PDT), aarklon@gmail.com wrote:

Primary concern: You need two versions of the program. How do you
confirm they are truly equivalent and that each is really coded for
highest efficiency?

Secondary concerns: On which hardware? Using which operating system?
Using which compiler? With what options? Which measure of speed, CPU
time or wall clock?

Are you getting the hint that there is no general answer?

Remove del for email

Recursive programs can be faster than the iterative versions when the
only changes you have introduced in the iterative version is saving
and restoring states. The system is of course faster in performing
push and pop as it simply means issuing 1 or 2 machine instructions.
In case of factorials, the stack frame is completely unnecessary. So
the iterative version is magnitudes faster than the recursive one.

Towers of Hanoi is faster in recursive version than the iterative one.
I am not sure about the quick sort. I will have to profile it but
surely the recursive version is more clear than the iterative one.

aarklon@gmail.com wrote:

Iterative mergesorts that I've seen for arrays,
tend to split less evenly than the recursive versions do.

When I race array sorting functions,
I can't get any speed from the iterative mergesorts.

I still haven't figured out how to mergesort a linked list iteratively.

pete wrote:

See the thread "Mergesort algorithm for linked lists"
from January 2007 in this newsgroup.

Try doing a BFS (Breadth First Search) or DFS of a dense graph
recursively
and iteratively (using lists) you will see a lot of difference.

Thanks,
Vamsi Kundet.

On Jun 2, 3:29 am, aark...@gmail.com wrote:

I can think of two:

1) Return the ith term of a fibonacci.



No, seriously. Its a matter of *WHICH* recursive formula you use.
There is a quadratic formula for {fib(n+1),fib(n)} in terms of
{fib(floor(n/2)+1),fib(floor(n/2))} which means that you can calculate
fib(n) in O(log(n)) steps (using recursion) instead of O(n) steps as
is usually the case with the typical iterative solution. For very
large n in big integer systems this is, in fact, that fastest
algorithm I know of for calculating fib(n). Anywhere where the direct
exponential formula can be used (when n is relatively small), tables
can also be used and are tremendously faster.

pete wrote:

I posted a complete linked list mergesort here one or two weeks
ago.