Recursion slows down mysteriously

This is a discussion on Recursion slows down mysteriously within the C++ Programming forums, part of the General Programming Boards category; Hi, I'm using a recursive algorithm that seemed to work quite well when called from my main() function, but now ...

  1. #1
    Registered User
    Join Date
    Jul 2002
    Posts
    17

    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.

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    You can always try modern compiler...
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by brane_sail View Post
    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.
    It makes no difference where it is called from. You're obviously calling it differently from subfunc. Show the code.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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 . . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by dwks View Post
    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.

  6. #6
    Registered User
    Join Date
    Jul 2002
    Posts
    17
    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

  7. #7
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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.
    That doesn't sound like enough local variables to cause much of a problem.

    Maybe you should post your code, if you feel comfortable doing so. Pseudo-code has a nasty habit of not translating perfectly into real code. Don't worry too much about length, unless it's say over 1,000 lines long. Then it might be better to just attach it.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    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...

  9. #9
    Registered User
    Join Date
    Jul 2002
    Posts
    17
    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.

  10. #10
    Registered User
    Join Date
    Jul 2002
    Posts
    17
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 08:45 PM
  2. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 08:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 01:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21