Thread: Functions calling themselves...?

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

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.

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.