Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Afaik

Deep recursive functions

This topic is 5371 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a recursive function that recurses a couple thousand times, and the program dies soon after. The problem is I can''t limit the depth. The program has to be allowed to recurse as deep as it wants so it can finish, or the operation is useless to me. How can fix something like this?

Share this post


Link to post
Share on other sites
Advertisement
Make it a tail recursion. And use O''Caml. No call limit anymore.

That, or use your own stack object and convert your recursive solution to an iterative one.

ToohrVyk

Share this post


Link to post
Share on other sites
To explicate what other posters have said:

I''m guessing you''re using C/C++. These languages do not take as well to recursion as other languages such as Lisp/OCaml/Scheme/many others, because they require you to keep around stack information for the different levels of recursion, even when you don''t need it. Because of this, it''s often better to recode your recursive algorithm into an iterative form. ANY recursive algorithm can be converted into an iterative algorithm, but some of them require you to use a stack. Here''s some more info.


How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
Are there any general textbook steps to converting a recursive function to an iterative one?

My searches show many examples of what recursive function
looks like when converted to an iterative one, but I can't find
any general information on what steps to take.

[edited by - afaik on September 21, 2003 11:37:50 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Sneftel
NY recursive algorithm can be converted into an iterative algorithm, but some of them require you to use a stack.

Ah, but there are times where the iterative form is much slower than the recursive, and thus useless. I'm currently using a recursive algorithm that can't be rewritten in an iterative form without making it too slow to be useful. Of course, this is more of an issue with the C++ language itself than recursion/iteration...


- Houdini



[edited by - Houdini on September 22, 2003 1:18:55 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Houdini
Ah, but there are times where the iterative form is much slower than the recursive, and thus useless.

That just means you''re doing it wrong. Assuming a decently programmed stack implementation, the two should be comparable in speed. And anything that can make use of tail-recursion doesn''t even need a stack.



How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
Ok, here's what my recursive function looks like when it has been gutted:


void
MyFunc(PARAMS *params) {

// return here when done
if(NULL == params) return;

for(i=0; i < params->count; i++) {
MyFunc(params);
}
}


Not sure where to start to make it into an iterative one.

[edited by - afaik on September 22, 2003 2:14:29 PM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!