Functions calling themselves...?

This is a discussion on Functions calling themselves...? within the C++ Programming forums, part of the General Programming Boards category; is it legal for a function to call itself as in: int sum(int n) { if(n==0) return 0; else n+sum(n-1); ...

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    18

    Functions calling themselves...?

    is it legal for a function to call itself as in:

    int sum(int n)
    {
    if(n==0)
    return 0;
    else
    n+sum(n-1);
    }

    wouldn't this be an infinite loop cuz it keeps calling itself?

  2. #2
    Unregistered
    Guest
    >is it legal for a function to call itself as in:
    Yes, it's called recursion.

    >wouldn't this be an infinite loop cuz it keeps calling itself?
    Recursive functions have to have an exit condition or this will happen.

  3. #3
    Registered User
    Join Date
    Jan 2002
    Posts
    18
    so without an exit(1) statement, it would be an infinite loop...?
    thanks, I get it now.

  4. #4
    Unregistered
    Guest
    not exactly, a recursive function works because it essentially creates a new instance of all of the automatic variables each time it's called. To stop it from calling itself it needs a condition to return and go back through each instance in reverse order.
    Code:
    call 1
      call 2
        call 3
          call 4
          meets condition
        call 3
      call 2
    call 1
    end
    The condition in your example was
    if(n==0)
    return 0;

  5. #5
    Registered User
    Join Date
    Dec 2001
    Posts
    421
    exit(1); exits your program.. you dont do that each time you use a recursive function. Just make sure that the function stops calling itself at some stage, and all will be fine

    check out my sig

    U.
    Quidquid latine dictum sit, altum sonatur.
    Whatever is said in Latin sounds profound.

  6. #6
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    ok people seem to be having trouble grasping recursion.
    For recursion you need two things.....

    1) A base case.

    2) Being able to simplify the problem.

    for example the factorial function (recursive)...
    lets say that x is the factorial we want to find.

    what is the base case?

    for this the base case is if x is equal to 0 or x is equal to 1 we return 1.

    i.e. 0! = 1 1! = 1

    so how do we simplify?

    well in this case 2! is equal to 2*1!
    3! is equal to 3*2!
    4! is equal to 4*3!
    5! is equal to 5*4!
    starting to see the pattern???

    so in code...
    Code:
    unsigned long int Factorial ( int x )
    {
    if ( x == 0 || x == 1) return 1; // the base case
    else
    //simplify the problem
    return ( x * Factorial ( x - 1 ));
    }
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  7. #7
    Seņor Member
    Join Date
    Jan 2002
    Posts
    561
    Maybe it's just me, but it seems more effieient to use loops instead of recursion; sure they involve more code but they don't use all that stack space. So for what reasons do we use recursion other than to shorten code?

  8. #8
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    Ease. Some stuff works really nice with recursion.

    Take for instance this iterative in order traversal of a binary tree from here http://www.gamedev.net/reference/pro...ees2/page4.asp

    Code:
    inline void inorderIterative( void (*process)(dataType& item) )
    {
        node* current;
        current = m_root;
        if( current != 0 )
        {
            while( current->m_left != 0 )
                current = current->m_left;
            while(1)
            {
                process( current->m_data );
                if( current->m_right != 0 )
                {
                    current = current->m_right;
                    while( current->m_left != 0 )
                        current = current->m_left;
                }
                else
                {
                    if( current->isLeft() )
                    {
                        current = current->m_parent;
                    }
                    else
                    {
                        while( current->isRight() )
                            current = current->m_parent;
                        if( current->isRoot() )
                            return;
                        current = current->m_parent;
                    }
                }
            }
        }
    }
    Can be written recursively as

    Code:
    void inorderRecursive( void (*process)(dataType&), node* cur) {
         if (cur != 0) {
             inorderRecursive(process, cur->m_left);
             process(current->m_data);
             inorderRecursive(process, cur->m_right);
        }
    }
    Usually when something can be done with tree recursion (IE, multiple recursive calls, rather than one recursive call in a function) making it iterative is error prone.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  9. #9
    Seņor Member
    Join Date
    Jan 2002
    Posts
    561
    Hehe I'm a newbie and I don't understand some of that code, but yes I can see how much it shortens and eases the code. But isn't recursion really clunky and inneficient when it is run (especially with large numbers) because it uses so much stack space? So it won't work well at all in scenarios using much more data?

  10. #10
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    It depends on how deep the recursion gets. For a balanced tree with n elements, a tree traversal like that will only require O(lg(n)) (for 1000 elements, it would take have about 10 function calls on the stack at one time maximum, for 1000000 elements, it would take about 20 function calls on the stack max) stack space, which basically means that the function can handle an extremely large amount of data before stack space really needs to be taken into consideration, and by the time you have to worry about stack space, you've probably already exhausted the conventional memory with the data. They wrote it from the point of view of optimizing for small computers, hand helds, gameboy, etc, in which the stack is generally limited.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  11. #11
    Registered User
    Join Date
    Dec 2001
    Posts
    421
    that's why we are programmers, and my mother isn't (no offence mum). We get to decide what is best for what scenario... and we implement that...

    if you know that you are going to be writing code that has millions of iterations.. then dont use recursion... if you think it's appropriate then use it!!!

    there is more to recursion that just tree traversal.. you'll see it more the more you code.

    it's a very good thing to know.

    good luck
    U.
    Quidquid latine dictum sit, altum sonatur.
    Whatever is said in Latin sounds profound.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 04-12-2009, 05:49 PM
  2. Replies: 9
    Last Post: 01-26-2008, 02:12 AM
  3. calling functions: exit and return
    By 911help in forum C Programming
    Replies: 3
    Last Post: 12-28-2007, 12:24 PM
  4. I Need Help Defining and Calling Functions
    By jonbuckets in forum C++ Programming
    Replies: 6
    Last Post: 10-25-2007, 09:46 AM
  5. Calling functions help
    By ForlornOdium in forum C++ Programming
    Replies: 14
    Last Post: 09-29-2003, 08:40 PM

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