Hi all,

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

aarklon@gmail.com wrote:
> Hi all,
>
> can any one give a example program where recursive version is faster
> than iterative version ?

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

Bartc said:

> aarklon@gmail.com wrote:
>> Hi all,
>>
>> can any one give a example program where recursive version is faster
>> than iterative version ?
>
> For trivial programs there may or may not be examples where recursion is
> faster.

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

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

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:

unsigned long factorial(unsigned long n)
{
return n < 2 ? 1 : (n * factorial(n - 1));
}

is horribly inefficient compared to its iterative version (and more so,
compared to the Stirling Approximation). In a production environment, it
would be inappropriate. But in a teaching environment, it might well be
considered a reasonable way to /illustrate/ recursion, given suitable
"don't do factorials this way in Real Life" caveats.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

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

>Hi all,
>
>can any one give a example program where recursive version is faster
>than iterative version ?

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:
> Hi all,
>
> can any one give a example program where recursive version is faster
> than iterative version ?

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

pete wrote:
> aarklon@gmail.com wrote:
>> Hi all,
>>
>> can any one give a example program where recursive version is faster
>> than iterative version ?
>
> 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.

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

--
Eric Sosman
esosman@ieee-dot-org.invalid

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

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.