# Functions calling themselves...?

• 01-17-2002
mikebrewsj
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?
• 01-17-2002
Unregistered
>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.
• 01-17-2002
mikebrewsj
so without an exit(1) statement, it would be an infinite loop...?
thanks, I get it now.
• 01-17-2002
Unregistered
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;
• 01-17-2002
Uraldor
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.
• 01-17-2002
Stoned_Coder
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 )); }```
• 01-17-2002
tim545666
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?
• 01-17-2002
SilentStrike
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.
• 01-17-2002
tim545666
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?
• 01-18-2002
SilentStrike
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.
• 01-18-2002
Uraldor
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.