|  | example program | | |
| | | Guest |  |
|  Posted: Mon Jun 02, 2008 10:29 am Post subject: example program |  |
Hi all,
can any one give a example program where recursive version is faster
than iterative version ? |
| |
| | | Bartc | |
| | Posted: Mon Jun 02, 2008 10:29 am Post subject: Re: example program | |
aarklon@gmail.com wrote:
| Quote: | 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 |
| |
| | | Richard Heathfield | |
| | Posted: Mon Jun 02, 2008 10:29 am Post subject: Re: example program | |
| |  | |
Bartc said:
| Quote: | 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/.
| Quote: | 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 |
| |
| | | Barry Schwarz | |
| | Posted: Mon Jun 02, 2008 10:29 am Post subject: Re: example program | |
On Mon, 2 Jun 2008 03:29:17 -0700 (PDT), aarklon@gmail.com wrote:
| Quote: | 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 |
| |
| | | pete | |
| | Posted: Mon Jun 02, 2008 11:10 am Post subject: Re: example program | |
aarklon@gmail.com wrote:
| Quote: | 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 |
| |
| | | Eric Sosman | |
| | Posted: Mon Jun 02, 2008 11:28 am Post subject: Re: example program | |
pete wrote:
| Quote: | 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 |
| |
| | | rahul | |
| | Posted: Mon Jun 02, 2008 11:57 am Post subject: Re: example program | |
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. |
| |
| | | vamsi.krishnak@gmail.com | |
| | Posted: Mon Jun 02, 2008 3:47 pm Post subject: Re: example program | |
| Quote: | 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. |
| |
| | | Paul Hsieh | |
| | Posted: Mon Jun 02, 2008 4:57 pm Post subject: Re: example program | |
| | | |
On Jun 2, 3:29 am, aark...@gmail.com wrote:
| Quote: | Can any one give a example program where recursive version is faster
than iterative version ?
|
I can think of two:
1) Return the ith term of a fibonacci.
<Pause for effect>
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.
2) In the newsgroup comp.programming, a challenge was recently posted
there which asked how to output the nodes of a binary search tree in
order without using any recursion or a growable stack/array. My
solution which did not modify the tree (imagine that the tree was a
mapping of URLs or was in ROM or through a file system with no write
permissions) took O(n*log(n)) time, and AFAIK, was not improved upon.
However, the recursive solution takes O(n) time.
--
Paul Hsieh
LINK
LINK |
| |
| | | CBFalconer | |
| | Posted: Mon Jun 02, 2008 6:30 pm Post subject: Re: example program | |
pete wrote:
| Quote: | aarklon@gmail.com wrote:
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.
|
I posted a complete linked list mergesort here one or two weeks
ago.
--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from LINK ** |
| |
| Page 1 of 3 .:. Goto page 1, 2, 3 Next | |
|
|
