Thread: Recursion

  1. #1
    Registered User
    Join Date
    Nov 2001


    Hey everyone,

    Never really done much recursion in C++ before but i just wrote a little depth first search which crashes the 1000th time it calls itself. Everytime. Stack Overflow is the error message.

    Is the stack limit 1000 or something?

    I'm using VC++ 6.0 on Win 2K.

    Shud I be able to do recursion with more than 1000 levels?

    Otherwise i'll have to attempt some non-recursive way which probably won't look as nice......

    Any thoughts wud b well welcome.

    Play it again Sam, HARDER!

  2. #2
    Registered User Nova_Collision's Avatar
    Join Date
    Feb 2003
    There is no static "limit" to recursion except memory. Remember that when you call a function, a copy of that function is loaded into RAM until the function completes. The only drawback to recursion is that no function completes until the final operation is done. That means that on the 1000th call, there is 1000 copies of the function in RAM. Depending on what your function does, you may simply be running out of memory.
    When in doubt, empty your magazine - Murphy's Laws Of Combat #7

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    >Shud I be able to do recursion with more than 1000 levels?
    It depends on the implementation.

    >Otherwise i'll have to attempt some non-recursive way which probably won't look as nice......
    How many recursive calls do you make in the algorithm? There's a chance that you can remove one or more without too much difficulty.
    My best code is written with the delete key.

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Waterloo, Texas
    >> Is the stack limit 1000 or something?

    No. When your program starts up, the OS has allocated a certain amount of ram for stack use. Calling a function sets up a sub-stack-frame within this area which 'eats-up' this memory until the function returns. The size of the local variables that the function declares plays a direct role in how much stack space each function call will use up. This could be summed up roughly as:

    available_stack =
    stack_in_use - (number_of_calls * (variables + overhead))

    Where 'stack_in_use' is the amount being used by functions which called this one (ie: main()), and 'overhead' is (usually) 4 bytes that get pushed onto the stack to hold the return address that will be jumped to after the function returns.

    So when you're designing a recursive function, the main guidelines are:

    1) Declare as few local variables as possible within the function.
    2) Make sure the maximum # of possible recursions is a reasonable value.
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
        return std::pow
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;

  5. #5
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    also, when a process is created, in linux, there is a default limit, set for the amount of ram for a process to own. your user probably can not have more than a thousand copies of that function in memory (size wise).
    Last edited by chrismiceli; 03-23-2004 at 12:42 PM.
    Help populate a c/c++ help irc channel
    server: irc://
    channel: #c

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, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10: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, 09: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, 02:29 PM