| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"Allen" |
| Date: |
04 Apr 2004 12:04:07 PM |
| Object: |
naked func for "one-way recurrsion" |
Hi all,
I have a tree object I'm writing that searches itself using a recursive
search. Thing is, I'm wanting to also include the ability to simply
transfer execution if I want ("one-way recursion"). _One problem_ with
doing it this way is stack overflow.
What I'm thinking of doing is using "naked" function calls for the
recursive search so that if I want to simply transfer execution, I could
clean up the stack myself. This seems an acceptable solution to me but, I
would be interested in other's opinions of this and of other possible
approaches.
--
Best wishes,
Allen
.
|
|
| User: "Gernot Frisch" |
|
| Title: Re: naked func for "one-way recurrsion" |
05 Apr 2004 04:32:39 AM |
|
|
"Allen" <allen-terri-ngNO!@#SPAMworldnet.att.net> schrieb im
Newsbeitrag
news:beXbc.34222$He5.655362@bgtnsc04-news.ops.worldnet.att.net...
Hi all,
I have a tree object I'm writing that searches itself using a
recursive
search. Thing is, I'm wanting to also include the ability to simply
transfer execution if I want ("one-way recursion"). _One problem_
with
doing it this way is stack overflow.
Think of this flood fill:
void Fill(long x, long y)
{
Fill(x+1, y); Fill(x, y+1); ...
}
Now, you could do this:
queue<points> have_to_fill;
have_to_fill.add_last(pt);
while(have_to_fill.size())
{
fill_around_first_of_queue_and_append_to_last(&have_to_fill);
have_to_fill.remove_head();
}
Know what I mean? Use a dymanic array instead of recursion if you fear
a stack overflow.
HTH,
--
-Gernot
Post here, don't email. If you feel you have to mail, revert my
forename from:
tonreG.Frisch.at.Dream-D-Sign.de@invalid.com
________________________________________
Looking for a good game? Do it yourself!
GLBasic - you can do
www.GLBasic.com
.
|
|
|
|
| User: "David Harmon" |
|
| Title: Re: naked func for "one-way recurrsion" |
04 Apr 2004 01:23:03 PM |
|
|
On Sun, 04 Apr 2004 17:04:07 GMT in comp.lang.c++, "Allen"
<allen-terri-ngNO!@#SPAMworldnet.att.net> wrote,
Hi all,
I have a tree object I'm writing that searches itself using a recursive
search. Thing is, I'm wanting to also include the ability to simply
transfer execution if I want ("one-way recursion"). _One problem_ with
doing it this way is stack overflow.
What I'm thinking of doing is using "naked" function calls for the
recursive search so that if I want to simply transfer execution, I could
clean up the stack myself. This seems an acceptable solution to me but, I
would be interested in other's opinions of this and of other possible
approaches.
What the heck are you talking about doing? There are quite a few terms
and phrases in your post that are unclear to me, such as
"naked function"
"transfer execution"
"one-way recursion"
"clean up stack myself"
The best way to "clean up the stack" is to return from the function.
The second best way is to throw an exception and catch it in the caller.
A very distant third is setjump/longjump, and don't even consider it.
There is no fourth way.
The whole point of having a stack is so that you can get back where you
came from. If you don't intend to return, you wouldn't use a recursive
call in the first place, but just search using a loop.
A typical case would be where you want to search for something and when
it is found stop looking. This is implemented by returning the thing
found from your recursive search, until you return to the top level,
which then uses the result or performs the desired operation upon it.
.
|
|
|
| User: "Allen" |
|
| Title: Re: naked func for "one-way recurrsion" |
04 Apr 2004 02:25:46 PM |
|
|
"David Harmon" <source@netcom.com> wrote in message
news:407a4f26.48324313@news.west.earthlink.net...
On Sun, 04 Apr 2004 17:04:07 GMT in comp.lang.c++, "Allen"
<allen-terri-ngNO!@#SPAMworldnet.att.net> wrote,
Hi all,
I have a tree object I'm writing that searches itself using a
recursive
search. Thing is, I'm wanting to also include the ability to simply
transfer execution if I want ("one-way recursion"). _One problem_ with
doing it this way is stack overflow.
What I'm thinking of doing is using "naked" function calls for the
recursive search so that if I want to simply transfer execution, I could
clean up the stack myself. This seems an acceptable solution to me but,
I
would be interested in other's opinions of this and of other possible
approaches.
What the heck are you talking about doing? There are quite a few terms
and phrases in your post that are unclear to me, such as
"naked function"
"transfer execution"
"one-way recursion"
"clean up stack myself"
The best way to "clean up the stack" is to return from the function.
The second best way is to throw an exception and catch it in the caller.
A very distant third is setjump/longjump, and don't even consider it.
There is no fourth way.
The whole point of having a stack is so that you can get back where you
came from. If you don't intend to return, you wouldn't use a recursive
call in the first place, but just search using a loop.
A typical case would be where you want to search for something and when
it is found stop looking. This is implemented by returning the thing
found from your recursive search, until you return to the top level,
which then uses the result or performs the desired operation upon it.
I looked up "naked" in my docs and found out it is platform
specific--sorry, didn't realize it was.
__declspec(naked) causes the compiler to emit code without a
prolog/epilog allowing you to write your own in asm. What I'm wanting to do
is have a recursive function that I don't have to "un-wind" from if I don't
want to. If I decide that I don't want to return then, I need some way of
removing the return data from the stack. Ugly--I know.
Using a loop to search implies an external object acting on a data set
(doesn't it?). What I'm trying to write is a "self-searching data set" with
some "ANN-ish" ideas thrown in as well (Artificial Neural Net). I need the
ability to either search or execute code--even that's not a real good
explanation of what I'm writing.
I know I've probably butchered numerous terms and not been very clear;
this is the best I can explain without boring everyone. The question
concerns the use of naked functions in my recursive search. Obviously, I
need to be very careful handling the stack. Do you see any other specific
problems with this?
--
Best wishes,
Allen
.
|
|
|
| User: "David Harmon" |
|
| Title: Re: naked func for "one-way recurrsion" |
04 Apr 2004 03:13:41 PM |
|
|
On Sun, 04 Apr 2004 19:25:46 GMT in comp.lang.c++, "Allen"
<allen-terri-ngNO!@#SPAMworldnet.att.net> wrote,
Using a loop to search implies an external object acting on a data set
(doesn't it?). What I'm trying to write is a "self-searching data set" with
some "ANN-ish" ideas thrown in as well (Artificial Neural Net).
No, a loop could just as easily be in a member function.
concerns the use of naked functions in my recursive search. Obviously, I
need to be very careful handling the stack. Do you see any other specific
problems with this?
Well, you asked for opinions and you've got mine: just say no. "Naked"
functions sounds like a good way for the compiler to let you implement
specific low-level necessarily platform specific things e.g. interrupt
handlers, and a really lousy thing to use in ordinary application code.
Among the great many problems with it are:
- It would be a huge effort to check for objects on the stack needing
destruction and properly call their destructors. The compiler will do
that for you. Not doing that is simply wrong.
- Murphy's law sez that as soon as you have put all that effort into
writing platform specific code, you will discover a need for a
platform-independent solution.
Returning from the function is quick and easy and I haven't heard
anything from you that suggests to me that you need anything else.
If nothing else, write it that way first and get it working.
Don't optimize before profiling.
.
|
|
|
|
|
|
|
Related Articles |
|
|
