473,899 Members | 3,419 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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,
goes quadratic on worst cases,
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)
A Killer Adversary for Quicksort
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
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>
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)
A Killer Adversary for Quicksort
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.

Similar topics

12
2772
by: da Vinci | last post by:
Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it?
43
4190
by: Lorenzo Villari | last post by:
I've tried to transform this into a not recursive version but without luck... #include <stdio.h> void countdown(int p) { int x;
0
1900
by: Ray Wesley Kinserlow Jr. | last post by:
We have been studying tail recursion in my computer class. The prof told us that some compilers will turn a tail recursion into an iteration thus allowing many, many function calls to the recursion. I have proved to myself that the two flavors of VC++ I have will do this but I cannot get the GNU G++ compiler to do so. It is run in unix on a sun sparc and is version 3.3.2. It's threading is POSIX. Is there a switch which will compile a...
18
3731
by: MTD | last post by:
Hello all, I've been messing about for fun creating a trial division factorizing function and I'm naturally interested in optimising it as much as possible. I've been told that iteration in python is generally more time-efficient than recursion. Is that true? Here is my algorithm as it stands. Any suggestions appreciated!
20
3015
by: athar.mirchi | last post by:
..plz define it.
30
8328
by: Jeff Bigham | last post by:
So, it appears that Javascript has a recursion limit of about 1000 levels on FF, maybe less/more on other browsers. Should such deep recursion then generally be avoided in Javascript? Surprisingly, deep recursion actually isn't that slow for what I'm doing. Programming this task recursively is so much more straightforward to me, but currently I'm forced to use an ugly hack to avoid going over the 1000 level limit. Of course, it could...
10
5507
by: slix | last post by:
Recursion is awesome for writing some functions, like searching trees etc but wow how can it be THAT much slower for computing fibonacci- numbers? is the recursive definition counting fib 1 to fib x-1 for every x? is that what lazy evaluation in functional languages avoids thus making recursive versions much faster? is recursive fibonacci in haskell as fast as an imperative solution in a procedural language?
35
4760
by: Muzammil | last post by:
int harmonic(int n) { if (n=1) { return 1; } else { return harmonic(n-1)+1/n; } } can any help me ??
0
9997
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9845
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11276
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9671
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
8043
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5891
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
4721
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4301
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3320
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.