• ### Popular Now

• 12
• 12
• 9
• 10
• 13

#### Archived

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

# Deep recursive functions

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

## 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 on other sites
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 on other sites
btw, I''m using C/C++.

What is tail recursion? What is O''Caml?

##### Share on other sites
Use a stack and a loop and rewrite the algorithm around those, not recursion.

##### 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 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 on other sites
Try:
...void recurse(int itnumber){    if(itnumber<MAX)        return;    ...}...recurse(0);...

##### 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 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 on other sites
Ok, here's what my recursive function looks like when it has been gutted:

voidMyFunc(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]