473,899 Members | 3,419 Online

# Iteration vs. Recursion

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?

I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here's a simple one I tried out:

#include<stdio. h>
/* To compare the the time and space cost of iteration against
recursion*/

const int SOME_CONST = 10;
void ifoo();
void rfoo(int, int, int);
int main(void)
{
ifoo();
rfoo(0, 0, 5);
printf("\n");
return 0;
}

void ifoo()
{
int i = 0, x = 0, y = 5;
for(; i < SOME_CONST; i++)
{
x += y;
printf("%d\t%d\ t%d\t\n", i, x, y);
}
}
void rfoo(int i, int x, int y)
{
x += y;
printf("\n%d\t% d\t%d", i, x, y);

if (i < SOME_CONST - 1)
rfoo(++i, x, y);
}
I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

b. Iteration preserves state, recursion does not.

May 8 '06
75 5671
Keith Thompson said:
I can write a Quicksort function if I have to -- but I don't have to.
And if I tried it without consulting any references, it's likely the
resulting function would have some (probably subtle) bugs.

I think that's unlikely - in the sense that I am quite confident your
function would sort correctly (after a few muffled curses and a bit more
typing, obviously).

I think it's far /more/ likely that it would in fact be a SlowSort, and that
you could easily write a Shell sort to out-perform it.

Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
fair bit harder.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
May 16 '06 #51

"Richard Heathfield" <in*****@invali d.invalid> wrote in message
news:94******** ************@bt .com...
Keith Thompson said:
I can write a Quicksort function if I have to -- but I don't have to.
And if I tried it without consulting any references, it's likely the
resulting function would have some (probably subtle) bugs.
I think that's unlikely - in the sense that I am quite confident your
function would sort correctly (after a few muffled curses and a bit more
typing, obviously).

I think it's far /more/ likely that it would in fact be a SlowSort, and
that
you could easily write a Shell sort to out-perform it.

Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
fair bit harder.

I guess you basic argument is something like - Efficiently is why academics
study such things. Programmers often only need concern themselves with
evaluating whether the algorithm is or is not in conflict with NP
completeness

When you define success that way, I doubt if anyone could possible disagree.

When I first started out (auto industry) success was often being able to
reduce the cost of a part by 1 cent (US). Efficency counted

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

May 16 '06 #52
David Lightstone said:
Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
fair bit harder.
I guess you basic argument is something like - Efficiently is why
academics study such things. Programmers often only need concern
themselves with evaluating whether the algorithm is or is not in conflict
with NP completeness

No, that's not what I'm saying at all. In fact, I was agreeing with the idea
that it's far better to write a call to qsort (possibly two minutes to bash
out a comparison function, and another twenty seconds to check the order of
the args in K&R) than to spend two hours getting Quicksort /wrong/. We all
know that Quicksort is faster than Shell sort, so it isn't a question of
choosing which algorithm to use. But having coded up a Shell sort just for
the hell of it, and then a Quick sort because I'm-so-smart-I-can, I was
astounded to discover that my Shell sort consistently outperformed my Quick
sort over a large range of data set sizes - tiny, through mid, and right
the way up to huge. Obviously I got my Quick sort wrong. It sorted just
fine, but it took way too long to do it.

When you define success that way, I doubt if anyone could possible
disagree.

When I first started out (auto industry) success was often being able to
reduce the cost of a part by 1 cent (US). Efficency counted

Yeah, but if saving a cent is success, then saving a dollar is a triumph.
The best way to make your sort Quick is to use the standard library's
sorting routine. That cuts down on writing time, debugging time, and run
time.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
May 16 '06 #53
Richard Heathfield wrote:
David Lightstone said:
Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
fair bit harder.

I guess you basic argument is something like - Efficiently is why
academics study such things. Programmers often only need concern
themselves with evaluating whether the algorithm is or is not in conflict
with NP completeness

No, that's not what I'm saying at all. In fact, I was agreeing with the idea
that it's far better to write a call to qsort (possibly two minutes to bash
out a comparison function, and another twenty seconds to check the order of
the args in K&R) than to spend two hours getting Quicksort /wrong/. We all

<snip>
When you define success that way, I doubt if anyone could possible
disagree.

When I first started out (auto industry) success was often being able to
reduce the cost of a part by 1 cent (US). Efficency counted

Yeah, but if saving a cent is success, then saving a dollar is a triumph.
The best way to make your sort Quick is to use the standard library's
sorting routine. That cuts down on writing time, debugging time, and run
time.

I agree completely. In addition, if after doing it you find your
libraries quicksort implementation isn't fast enough the best thing to
do is see if you can find a better one that someone else has implemented
and use that.

I'll never write code myself if I can find and legally use some written
by an expert in the field.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
May 16 '06 #54
Richard Heathfield wrote:
The best way to make your sort Quick is to use the standard library's
sorting routine.

The truth of that is entirely implementation dependant.

qsort on my implementation,
and it has more than one kind of worst case,
and it is easy to beat hand coded, for all cases.
Using
http://www.mindspring.com/~pfilandr/C/e_driver/

/* BEGIN e_driver.c program output */

Timing 4 different sorting functions.
Sorting arrays of N number of elements,
in 2 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
N qisort qrsort m_sort qsort
199998 0.110000 0.109000 0.140000 0.156000
199999 0.110000 0.125000 0.140000 0.157000
Total times:
qisort: 0.220000 qsort interface, center pivot introspective
qrsort: 0.234000 qsort interface, random pivot introspective
m_sort: 0.280000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 0.313000 standard library qsort

Distribution #2: Ramp, Drives center pivot qsorts, quadratic
N qisort qrsort m_sort qsort
199998 0.250000 0.094000 0.078000 0.922000
199999 0.266000 0.094000 0.078000 1.250000
Total times:
qisort: 0.516000 qsort interface, center pivot introspective
qrsort: 0.188000 qsort interface, random pivot introspective
m_sort: 0.156000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 2.172000 standard library qsort

/* END e_driver.c program output */
/* BEGIN e_driver.c program output */

Timing 4 different sorting functions.
Sorting arrays of N number of elements.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Two values, Badly written qsorts choke on this
N qisort qrsort m_sort qsort
19998 0.000000 0.000000 0.000000 1.594000
19999 0.000000 0.000000 0.000000 1.593000
Total times:
qisort: 0.000000 qsort interface, center pivot introspective
qrsort: 0.000000 qsort interface, random pivot introspective
m_sort: 0.000000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 3.187000 standard library qsort

/* END e_driver.c program output */

--
pete
May 16 '06 #55
pete said:
Richard Heathfield wrote:
The best way to make your sort Quick is to use the standard library's
sorting routine.

The truth of that is entirely implementation dependant.

Naturally, but:

(a) mostly it's true anyway;
(b) in cases where the implementation gives you a lousy qsort, get a better
implementation!

(a) takes care of maybe 90% of the cases. (b) takes care of maybe 90% of
what remains. And even if you're in the unlucky 1%, nevertheless you can
probably still find something on Usenet, written by some guy who calls
himself Lower Case Pete, which does the job for you. So there's no real
need to write it yourself.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
May 16 '06 #56
pete wrote:
Richard Heathfield wrote:
The best way to make your sort Quick is to use the standard
library's sorting routine.

The truth of that is entirely implementation dependant.

It is always possible to make quicksort go quadratic solely by the
appropriate input data. See:

SOFTWARE—PRACTI CE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999)
M. D. MCILROY
Dartmouth College, Hanover, NH 03755, USA

I have this as a file mdmspe.pdf on my system. Not sure where I
found it.

You can use sorts with guaranteed worst case performance, such as
heapsort and mergesort. There is no guarantee that the C system
qsort is actually quicksort.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
May 16 '06 #57

CBFalconer wrote:
pete wrote:
Richard Heathfield wrote:
The best way to make your sort Quick is to use the standard
library's sorting routine.
The truth of that is entirely implementation dependant.

It is always possible to make quicksort go quadratic solely by the
appropriate input data. See:
No, that's not true. If you partition on the median element,
you can guarantee O(n log n) - admittedly finding the median
in linear time is not so practical. Alternatively, if you
partition on a random element (using a good source of
randomness), no fixed input will make it go quadratic.
SOFTWARE-PRACTICE AND EXPERIENCE, VOL. 29(0), 1-4 (0 1999)
M. D. MCILROY
Dartmouth College, Hanover, NH 03755, USA

This is a great paper, but the technique only apply to a
certain (but broad) class of partitioning schemes.

May 16 '06 #58
Richard Heathfield <in*****@invali d.invalid> writes:
David Lightstone said:
Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
fair bit harder.

I guess you basic argument is something like - Efficiently is why
academics study such things. Programmers often only need concern
themselves with evaluating whether the algorithm is or is not in conflict
with NP completeness

No, that's not what I'm saying at all. In fact, I was agreeing with the idea
that it's far better to write a call to qsort (possibly two minutes to bash
out a comparison function, and another twenty seconds to check the order of
the args in K&R) than to spend two hours getting Quicksort /wrong/. We all
know that Quicksort is faster than Shell sort, so it isn't a question of
choosing which algorithm to use. But having coded up a Shell sort just for
the hell of it, and then a Quick sort because I'm-so-smart-I-can, I was
astounded to discover that my Shell sort consistently outperformed my Quick
sort over a large range of data set sizes - tiny, through mid, and right
the way up to huge. Obviously I got my Quick sort wrong. It sorted just
fine, but it took way too long to do it.

Some things to keep in mind:

The basic Quicksort algorithm is quadratic (O(N**2)) for some inputs.
There are various ways to tweak it to avoid this problem, such as
being smarter about picking a pivot value.

The best possible performance for a sorting algorithm (using only a
certain set of operations) is O(n log n). Quicksort isn't the only
O(n log n) sorting algorithm.

Despite the name, there is no requirement for C's qsort() function to
be implemented using the Quicksort algorithm. No sane implementer
would use a quadratic algorithm for qsort(), but it would be legal.
(Perhaps the DS9K does this.)

The qsort() function does impose a significant performance overhead
compared to a hand-written sorting routine. It has to perform an
indirect function call for each comparison. If you re-implement the
exact same algorithm used by your implementation, but using inline
comparisons, you'll probably get a constant factor speedup. There are
undoubtedly cases where this would be worth doing -- *if* you've
measured the actual performance and determined that it's significant.

For sufficiently small arrays, the complexity of Quicksort and other
O(n log n) algorithms can make them slower than quadratic algorithms
like insertion sort. One common approach is to use Quicksort, but
fall back to something like insertion sort for small subarrays.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
May 17 '06 #59
"Googmeiste r" <go*********@gm ail.com> writes:
CBFalconer wrote:
pete wrote:
> Richard Heathfield wrote:
>> The best way to make your sort Quick is to use the standard
>> library's sorting routine.
>
> The truth of that is entirely implementation dependant.

It is always possible to make quicksort go quadratic solely by the
appropriate input data. See:

No, that's not true. If you partition on the median element,
you can guarantee O(n log n) - admittedly finding the median
in linear time is not so practical. Alternatively, if you
partition on a random element (using a good source of
randomness), no fixed input will make it go quadratic.

One approach I've seen is to take the median of the first, middle, and
last elements, and use that as the pivot.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
May 17 '06 #60

This thread has been closed and replies have been disabled. Please start a new discussion.