example program

[aarklon@gmail.com]

Hi all,

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

[Bartc]

Re: example program

aarklon@gmail.c om 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

[Richard Heathfield]

Re: example program

Bartc said:

aarklon@gmail.c om 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(unsig ned 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]

Re: example program

On Mon, 2 Jun 2008 03:29:17 -0700 (PDT), aarklon@gmail.c om 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

[rahul]

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.

[pete]

Re: example program

aarklon@gmail.c om 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

[Eric Sosman]

Re: example program

pete wrote:

aarklon@gmail.c om 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

[vamsi.krishnak@gmail.com]

Re: example program

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.

[CBFalconer]

Re: example program

pete wrote:

aarklon@gmail.c om 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 http://www.teranews.com **

[Chris Thomasson]

Re: example program

<aarklon@gmail. comwrote in message
news:b338ac82-d1d7-42ec-bda7-380f0d36111c@i3 6g2000prf.googl egroups.com...

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

IMVHO, it's not really a matter of whether recursion is faster than
iteration, but which one is "safer" in practice... Recursion has a
side-effect of blowing the stack on some platforms when the depth exceeds
the stack size of the calling thread. This does not happen for iteration;
here is an example:

http://groups.google.com/group/comp.lang.c/msg/edee8351e006ff16

IMO, using iteration is safer than recursion when traversing a tree. On some
platforms, passing a "large enough" tree to a recursive traversal function
can result in a seg-fault.

[Paul Hsieh]

Re: example program

On Jun 2, 4:43 am, Richard Heathfield <r...@see.sig.i nvalidwrote:

Bartc said:

aark...@gmail.c om 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/.

That is because a lot of real world programming revolved around the
idiom that 4 billion is the same as infinity.

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(unsig ned 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.

The above is bad because it pushes onto the stack once for each value
of n. But its a straw man against recursion in general.

If we were using arbitrary precision numbers, then matters would be
quite different. So if we assume that multiplier is somewhere between
O(bits**2) and O(bits) where bits is the larger of the two operands,
what *is* the fastest way to do factorial?

Hint:

(551!)**2 ~~ 1000!
(5405!)**2 ~~ 10000!
(53193!)**2 ~~ 100000!

etc.

If we break the factorial down into multiplying sequence halves, then
we have a *recursive* solution that it probably not too bad.

--
Paul Hsieh

http://www.pobox.com/~qed/

http://bstring.sf.net/

[Richard Heathfield]

Re: example program

Paul Hsieh said:

On Jun 2, 4:43 am, Richard Heathfield <r...@see.sig.i nvalidwrote:

<snip>

>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(unsig ned 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.

>
The above is bad because it pushes onto the stack once for each value
of n.

It's only bad if your objective is efficiency. If the objective is to
explain recursion, there's nothing wrong with it at all. The part you
snipped made it clear that this was in fact my point: "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."

But its a straw man against recursion in general.

But it wasn't intended to be an argument against recursion in general! It
was an illustration that even in situations such as factorial calculation,
where recursion is generally considered (by the clueful) to be bad, there
can still be times where it's useful to do it anyway. There are plenty of
examples where recursion is *not* generally considered (by the clueful) to
be bad.

In fact, your reply to my article seems to be based on a complete
misunderstandin g of what I actually wrote.

If we were using arbitrary precision numbers, then matters would be
quite different. So if we assume that multiplier is somewhere between
O(bits**2) and O(bits) where bits is the larger of the two operands,
what *is* the fastest way to do factorial?

Still the Stirling Approximation.

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

[Chris Thomasson]

Re: example program

"Paul Hsieh" <websnarf@gmail .comwrote in message
news:4c051b7e-8748-424c-a249-5730596fa303@w5 g2000prd.google groups.com...

On Jun 3, 4:49 am, "Chris Thomasson" <cris...@comcas t.netwrote:

[...]

>Did your solution use something similar to the following technique:
>>
>http://groups.google.com/group/comp....ee8351e006ff16
>>
>I basically add an auxiliary pointer per-node and use that as a link in a
>traversal queue. I believe that is easier than explicitly threading the
>tree.

>
No, mine did not augment or write to the tree at all. It uses O(1)
space:
>

http://www.azillionmonkeys.com/qed/treeO1.c

>
In any event, the recursive solution is *faster* than this which is
what the OP was looking for. I just happen to be able to demonstrate
that "this" even existed.

Nice. I need to really take a look at your code.

[...]

[pete]

Re: example program

Eric Sosman wrote:

pete wrote:

>aarklon@gmail.c om 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.
>

Thanks.
I recall taking a look and not liking it.
I'll have to take another look
and make a record of what I don't like,
if that turns out to still be the case.

--
pete

[pete]

Re: example program

CBFalconer wrote:

pete wrote:

>aarklon@gmail.c om 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.

Under what situations, if any,
would you be more inclined to use an iterative mergesort
than a recursive mergesort, on a list?

--
pete