Thread: Recursion vs multiple functions

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    Recursion vs multiple functions

    Just a quick question on recursion. Does it make a difference in terms of speed/resourses/memory/whatever if one uses recursion instead of multiple functions if they both do the same thing? Like for example in this example:
    Code:
    // if one assumes x is 2
    int recursiveFunc(int x)
    {
       if (x==0)
         return 0;
       else
         return recursiveFunc(x-1);
    }
    versus
    Code:
    // if one assumes x is 2
    int func1()
    {
        return func2();
    }
    int func2()
    {
        return func3();
    }
    int func3()
    {
       return 0;
    }
    I agree that this is a stupid useless example, but it was the first thing that came to mind

    Both examples do the same thing, but aside from readability and the fact that the recursive one works for more values of x, is one of these faster/better than the other? I'm just not sure if the computer treats recursion as just another function call or if something different is done. Hope this makes sense...

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    It's just another function all. The calling method is general enough so that it doesn't matter which function is called from which function.

    The recursive code with x = 2 will end up having to do a check to stop the recursion, while the non-recursive function can tell how many more functions to call, which favors the non-recursive function. However, the recursive function exist only once in the binary, while func1, func2, and func3 all exist in the binary causing it to be larger than just, say, having func1.

    Generally, I'd say just use whatever produces code that is easier to follow. If it happens to be recursion, use it, if it happens to be iteration, use it. Unless it's too slow, leave it there.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    No. All a function call does is toss data on the stack and jumps to some code -- whether you are calling the same function or a different one it does exactly the same thing. The question you probably should be asking is "is a loop better than recursion," which is "yes" in most cases... as long as it makes sense to do so.

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Right. Generally, a recursive function will replace a loop and vice versa. The main consideration with recursion is how often will we recurse till we return from a call? The reason is, every time you enter the recursive function, variables in that function are created from the stack, and they won't be freed till the function returns, so that if we enter the recursion say, 100,000 times without returning even once, we have 100,000 copies of those variables, which obviously eats up the stack quite quickly. This would be the case for the recursion you gave, by the way. Other recursive functions, like quicksort, generally return from internal recursions quite frequently, and so are quite safe.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Okay, thanks all. This is for a connect four AI I'm writing which looks 8 plys deep, but this takes up a bit of time with recursion and I wasn't sure if it would speed up if I made each level a different function unto its own.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. returning multiple values from functions?
    By jamesn56 in forum C++ Programming
    Replies: 5
    Last Post: 08-23-2005, 01:10 PM
  2. Phantom redefinition
    By CodeMonkey in forum C++ Programming
    Replies: 6
    Last Post: 06-12-2005, 05:42 PM
  3. Linker errors - Multiple Source files
    By nkhambal in forum C Programming
    Replies: 3
    Last Post: 04-24-2005, 02:41 AM
  4. calling functions within functions
    By edd1986 in forum C Programming
    Replies: 3
    Last Post: 03-29-2005, 03:35 AM
  5. Passing data/pointers between functions #2
    By TankCDR in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 09:49 PM