example program

[aarklon]

Hi all,

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

[Bartc]

aa*****@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

[Richard Heathfield]

Bartc said:

aa*****@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

[Barry Schwarz]

On Mon, 2 Jun 2008 03:29:17 -0700 (PDT), aa*****@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

[rahul]

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]

aa*****@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

[Eric Sosman]

pete wrote:

aa*****@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
es*****@ieee-dot-org.invalid

[vamsi.krishnak]

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]

pete wrote:

aa*****@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 http://www.teranews.com **

[Chris Thomasson]

<aa*****@gmail.comwrote in message
news:b3**********************************@i36g2000 prf.googlegroups.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....ee8351e006ff16

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]

On Jun 2, 4:43 am, Richard Heathfield <[e-mail]:

Bartc said:

[e-mail] 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(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.

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]

Paul Hsieh said:

On Jun 2, 4:43 am, Richard Heathfield <[e-mail]:

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

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

"Paul Hsieh" <we******@gmail.comwrote in message
news:4c**********************************@w5g2000p rd.googlegroups.com...

On Jun 3, 4:49 am, "Chris Thomasson" <[e-mail]:

[...]

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

Eric Sosman wrote:

pete wrote:

>aa*****@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.

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]

CBFalconer wrote:

pete wrote:

>aa*****@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.

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

--
pete

[CBFalconer]

pete wrote:

CBFalconer wrote:

>pete wrote:

>>aa*****@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.

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

If you read the code, you will see that some routines are
iterative, in that they follow the list, and others are recursive.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

** Posted from http://www.teranews.com **

[rahul]

So basically if we try simply to convert a recursive solution to
iterative by manually creating a stack frame and simulating function
calls, the resulting code is both ugly and slow. But if obvious
optimizations can be done for the stack frame, and in some cases it is
even completely eliminated ( factorial ), then the iterative code is
more efficient. As per my understanding, there are various algorithms
in which recursive solutions are faster - towers of hanoi, BFS, DFS to
name a few.

The recursive solution for X is faster than iterative does not
necessarily mean it is faster. It may mean that an optimized iterative
algorithm is yet to be written. A bit off the topic, but many a times
tail recursion (where applicable) significantly increases the
execution speed. I think the choice between recursive and iterative
approach is highly situation dependent and there is no right answer.

[Richard Harter]

On Wed, 04 Jun 2008 03:27:23 -0400, CBFalconer
<cb********@yahoo.comwrote:

>pete wrote:

>CBFalconer wrote:

>>pete wrote:
aa*****@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.

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

If you read the code, you will see that some routines are
iterative, in that they follow the list, and others are recursive.

Your reply is non-responsive. He asked about when you would use
an iterative mergesort on a list. Your code was for a recursive
mergesort. Recursive mergesort implicitly requires a stack;
iteratative mergesort does not.
Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[CBFalconer]

Richard Harter wrote:

CBFalconer <cb********@yahoo.comwrote:

>pete wrote:

>>CBFalconer wrote:
pete wrote:
aa*****@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.

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

If you read the code, you will see that some routines are
iterative, in that they follow the list, and others are recursive.

Your reply is non-responsive. He asked about when you would use
an iterative mergesort on a list. Your code was for a recursive
mergesort. Recursive mergesort implicitly requires a stack;
iteratative mergesort does not.

If, instead of making silly comments, you read the code, you could
note that the routines revlist, mergelists, splitlist are all
iterative, and that only mergesort (which controls the others) is
actually recursive. The question did not involve a stack. The
following is the ONLY recursive component:

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **

[Richard Harter]

On Thu, 05 Jun 2008 09:48:30 -0400, CBFalconer
<cb********@yahoo.comwrote:

>Richard Harter wrote:

>CBFalconer <cb********@yahoo.comwrote:

>>pete wrote:
CBFalconer wrote:
pete wrote:
>aa*****@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.

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

If you read the code, you will see that some routines are
iterative, in that they follow the list, and others are recursive.

Your reply is non-responsive. He asked about when you would use
an iterative mergesort on a list. Your code was for a recursive
mergesort. Recursive mergesort implicitly requires a stack;
iteratative mergesort does not.

If, instead of making silly comments, you read the code, you could
note that the routines revlist, mergelists, splitlist are all
iterative, and that only mergesort (which controls the others) is
actually recursive. The question did not involve a stack. The
following is the ONLY recursive component:

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

Exactly. The algorithm you use is a recursive mergesort. The OP
was asking when you would use an iterative mergesort, i.e., one
that does use not use recursion. The fact that a lot of your
code uses iteration rather than iteration is irrelevant.


Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Richard Harter]

On Thu, 05 Jun 2008 15:32:41 GMT, cr*@tiac.net (Richard Harter)
wrote:

>Exactly. The algorithm you use is a recursive mergesort. The OP
was asking when you would use an iterative mergesort, i.e., one
that does use not use recursion. The fact that a lot of your
code uses iteration rather than iteration is irrelevant.

Er, that should be "iteration rather than recursion".

Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.