[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Re: recursion, stacksize & linux
From:       Leon Widdershoven <l.widdershoven () fz-juelich ! de>
Date:       2000-12-11 17:02:05
[Download RAW message or body]

No, I'm sorry. I'm not that much into compiler stuff. Though it
should be fairly simple if the maximum depth of the recursion
is known in advance (almost never I guess). Or of course the
property of the last iteration is known (like with fibonacy
numbers). But that is something only the programmer can tell...

Leon

David van Hoose wrote:
> 
> Very true. But I have never seen a compiler ever attempt to transform
> a recursion to a loop. Do you have any examples of functions that do
> this.
> I would like to see.
> 
> -Dave
> 
> Leon Widdershoven wrote:
> >
> > Transforming a recursive function to a loop looks like the
> > best solution; compilers tend/try to do this when optimizing the
> > code (if they see a way to do it). Function calls are quite
> > "expensive" compared to loops anyway. Though I admit that
> > mathematically a recursive function is more elegant:)
> >
> > Leon
> >
> > David van Hoose wrote:
> > >
> > > John Califf wrote:
> > > >
> > > > I have a question about recursion vis-a-vis a flood fill method for some
> > > > graphics apps (kiconedit and krayon).  Kiconedit uses a recursive flood
> > > > fill algorithm which is rather elegant and I ported it to krayon as
> > > > well.
> > > >
> > > > There is a problem with flooding large areas in this way, though, as
> > > > linux seems to exceed some kind of stack limit causing a crash.
> > > > Actually the app doesn't crash, but linux has a problem with the app
> > > > stack and/or memory.  I've worked around this by limiting the area that
> > > > can be flooded.  Not ideal, because it requires several clicks to get
> > > > some large areas filled.  This can be done more automatically using
> > > > sections (dividing screen up into rectangular areas and doing them
> > > > sequentially) but that isn't ideal either.
> > > >
> > > > Is there some kind of limit on stack size in linux, and if so, is there
> > > > some way to change it from within an application?  The recursion here
> > > > can be quite deep, thousands of levels deep, even hundreds of thousands
> > > > for large images.
> > > >
> > > > I noticed a gtk app that uses an artifical stack (just a large array) to
> > > > use a similar recursive algorithm for flood filling, and may try that
> > > > approach but the stack problem with linux bothers me.
> > > >
> > > > There is also a home-made algorithm I am working on which divides the
> > > > image into quadrants from where you click to flood, and works outwards
> > > > in each quadrant.  With this, there is no recursion and no stack
> > > > problem. However, it also requires lots of checks and in-line code which
> > > > is not as elegant as using recursion, and is probably a waste of my time
> > > > developing further if a more elegant recursive method can be used.
> > >
> > > How about transforming the recursive function to a loop?
> > > You don't have to worry about overruning the systems memory.
> > > And think about it. It will run faster too.
> > > If you need help with this, I'll take a look at the code.
> 
> >> Visit http://master.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<
 
>> Visit http://master.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<

[prev in list] [next in list] [prev in thread] [next in thread]