Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Converting recursive algorithm to an iterative version

Reply
Thread Tools

Converting recursive algorithm to an iterative version

 
 
Juha Nieminen
Guest
Posts: n/a
 
      12-10-2011
88888 Dihedral <(E-Mail Removed)> wrote:
> There are very limited cases for recursive functions to be used in C.


You don't understand my point.

> The quick sort in the c lib is notorious to be choked quite often.


qsort() is not slow because of the recursion. std::sort() uses recursion
as well. So what?
 
Reply With Quote
 
 
 
 
88888 Dihedral
Guest
Posts: n/a
 
      12-10-2011
On Saturday, December 10, 2011 6:33:15 PM UTC+8, Juha Nieminen wrote:
> 88888 Dihedral <(E-Mail Removed)> wrote:
> > There are very limited cases for recursive functions to be used in C.

>
> You don't understand my point.
>
> > The quick sort in the c lib is notorious to be choked quite often.

>
> qsort() is not slow because of the recursion. std::sort() uses recursion
> as well. So what?


There was not my problem. That was problems for non-professionals.
 
Reply With Quote
 
 
 
 
88888 Dihedral
Guest
Posts: n/a
 
      12-10-2011
On Saturday, December 10, 2011 6:41:28 PM UTC+8, 88888 Dihedral wrote:
> On Saturday, December 10, 2011 6:33:15 PM UTC+8, Juha Nieminen wrote:
> > 88888 Dihedral <(E-Mail Removed)> wrote:
> > > There are very limited cases for recursive functions to be used in C.

> >
> > You don't understand my point.
> >
> > > The quick sort in the c lib is notorious to be choked quite often.

> >
> > qsort() is not slow because of the recursion. std::sort() uses recursion
> > as well. So what?

>
> There was not my problem. That was a problem for non-professionals.


 
Reply With Quote
 
Tobias Müller
Guest
Posts: n/a
 
      12-10-2011
Juha Nieminen <(E-Mail Removed)> wrote:
> 88888 Dihedral <(E-Mail Removed)> wrote:
>> If you are writing programs to be run infrequently for trivial jobs,
>> I have to say that in this kind of trivial cases there is no need for
>> any optimization or improvement for this kind of programming.

>
> And my point is that *regardless* of where the code might be used,
> converting a naturally recursive algorithm into an iterative form that
> avoids the recursive function call is usually premature optimization of
> the bad kind (makes the code significantly more complicated for little
> to no benefit).


One can argue if it is an optimization at all, but why do you always call
it premature? In my understanding, premature optimization is optimization
that is done before knowing if it is really worth it. Bad quality alone
doesn't qualify an optimization as premature.

The OP has already said that he has encountered stack overflows, so I
really would not call that premature if he wants to do fix that.
You cannot always control the stack size awailable to a function especially
if you are writing a library and not an executable.

Tobi
 
Reply With Quote
 
Joe keane
Guest
Posts: n/a
 
      12-11-2011
In article <Xns9FB5D491D88E7myfirstnameosapriee@216.196.109.1 31>,
Paavo Helde <(E-Mail Removed)> wrote:
>Increasing the stack size should be relatively harmless unless the app has
>many threads.


That's what gets you...

Stack on multi-thread apps is demanding.

Even if some memory is needed for a short time, (heap is what the
threads need at the same time, stack is what all the threads need some
of the time) the heap allocation may be -faster- (because it uses memory
efficiently).

Also running out of stack is ungraceful... If you call malloc and it
returns NULL (oh wait this C++ you know what mean) you can try to
restore some semblance of order. Out of stack, blam! Your files,
shared memory??

I echo some other posters that we don't know the context of program.
Some app you only run yourself? Quasi-real-time where some people die
if it fails?
 
Reply With Quote
 
Ania
Guest
Posts: n/a
 
      12-11-2011
This app is just for my personal use and it works quite fast for data
sets < 50 000 items. However, for larger data sets I encountered stack
overflows and I was wondering if changing it to an iterative version
would solve the problem.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
DNS Question: Recursive vs. Iterative SWE MCSE 20 04-08-2011 06:29 PM
converting recursive function to iterative V C Programming 4 05-13-2008 02:08 PM
Re: Where to get stand alone Dot Net Framework version 1.1, version 2.0, version 3.0, version 3.5, version 2.0 SP1, version 3.0 SP1 ? PA Bear [MS MVP] ASP .Net 0 02-05-2008 03:28 AM
Re: Where to get stand alone Dot Net Framework version 1.1, version 2.0, version 3.0, version 3.5, version 2.0 SP1, version 3.0 SP1 ? V Green ASP .Net 0 02-05-2008 02:45 AM
Translation from recursive to iterative BQ C Programming 14 03-25-2005 10:53 AM



Advertisments