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?

>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.

so without an exit(1) statement, it would be an infinite loop...?
thanks, I get it now.

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;

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.

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 ));
}

---

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?

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.

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?

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.

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.