Thread: Recursion slows down mysteriously

Hi, I'm using a recursive algorithm that seemed to work quite well when called from my main() function, but now i'm trying to run through different scenarios and when i call it from another function (ie main() --> subfunc() --> recurs() ) it seems to have slowed down by at LEAST a factor of 10.

Has anyone had this problem before, perhaps with a compiler failing to optimize code that is not called directly from main()?

And i am using the borland command line compiler (think it is vers. 5?)

Thanks for any help you can shed on the subject.

Originally Posted by dwks

Well, it's possible that subfunc() is taking up a lot of stack space. That could affect it. However, the only thing I can see happening as a result of this is a segmentation fault, not a slow-down . . . .

If you "unlimit" the stack, which is possible on a lot of systems, and the default on some, then excessive use of stack will lead to tons of swapping, which would definitely be noticable.

Again, what kind of recursion is this, how deep does it go, what's the branching factor, do you have any very large local variables, etc.

okay, the program is calculating probabilities but is very clunky so here is some pseudo-code:

recurse(int i)
for (x=0; x<12; x++)
array[i]=x;
temp = test()
if(temp==0)
recurse(i+1);
else
results[temp]++

so the recursion ends up setting up like nested for-loops but it might go as deep as about 10 levels of recursion, depending on the results of the test() function.

My problem i ran into was this: i wanted to keep the "scenario managing" function clean so i set it up in main(). Then i set up a directional function, direct() that looked like so:

direct(int x)
switch(x)
case 1: call a set of routines
break;
case 2:....
case 3: recurse()
call other routines
break

so I would end up sending instructions from the "scenario builder" to the directional function, and it would parse out what action to take, and ultimately call the recursive function.

Overall the program has about 6 integer arrays with 15 to 30 elements each. One integer array of 50 elements, and a handful of other variables.

Sorry for the long post, but thanks for any help you can give

Code:

for (x=0; x<12; x++)
{
   array[i]=x;
   temp = test()
   if(temp==0)
       recurse(i+1);
   else
      results[temp]++
}

I see no explicit base case, but I suppose it happens when test() never returns 0. But at the worst case this recursion has a branching factor of 12, which means that if it goes 10 levels deep, there will be over 5 billion calls to recurse(). That might have something to do with it...

I am going to take one more crack at it before I go so far as to post the whole thing, as it is pretty complex and not very well commented

But i know that it is not a problem with the recursion in itself because I started out with the recursion alg. and ran it with some user inputs and it ran fine in about 1-1.5 seconds. But when i wrote another program to generate different inputs, and just changed the recursion one into a subroutine then it slowed down. But i will take another look at it before i give up and have someone else fix my code for me.

But thank you very much for the suggestions so far.

Okay, so i went back through the code, and after tightening it up a bit found that it was easier to avoid using the subroutine to call the recursion from. It works a little better now, but with all recursive methods of this type, it is very hard to predict how long any given call to it will take.

But thanks for all your help.