recursion call on exit

[glao]

Hello ,

I have this code:

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

 void message(int numbers)
 {

    cout << "Entry to function #" << numbers << endl;
    if ( numbers > 0 )
    {
        cout << "This is a recursive function." << endl;
        message( numbers-1 );
    }

    cout << "Exit from function #" << numbers << endl;
 }

int main() 
{
    message(4);

return 0;

}    

and the output is :

Entry to function #4
This is a recursive function.
Entry to function #3
This is a recursive function.
Entry to function #2
This is a recursive function.
Entry to function #1
This is a recursive function.
Entry to function #0
Exit from function #0
Exit from function #1
Exit from function #2
Exit from function #3
Exit from function #4

I would expect the : Exit from function to be executed only one time, when the numbers will be zero.

I can't understand how this is being executed ..When the numbers=0 , we have the Entry to funtion #0 and Exit from function #0.

[Reverend Jim]

There is only one way to exit from the function and that is by falling through to the end. That will happen once for every call to the function (including recursive calls).

[tinstaafl]

What you're seeing is one of the drawbacks to recursion. Each iteration means the another copy of the function is running until the last one exits. In some cases this can put an unrecoverable strain on resources.

[AssertNull]

I would expect the : Exit from function to be executed only one time

See Jim's post.

There is only one way to exit from the function and that is by falling through to the end.

 void message(int numbers)
 {

    cout << "Entry to function #" << numbers << endl;
    if ( numbers > 0 )
    {
        cout << "This is a recursive function." << endl;
        message( numbers-1 );
        return;  // missing this line
    }

    cout << "Exit from function #" << numbers << endl;
 }

I'm guessing the above is what you intended. It's common to return immediately after a recursive function call, but you weren't doing that. It's an easy mistake to make with a void function (assuming again that that is what your intent was). When your function returns something, you're less likely to accidentally NOT return from the function. See program below, based on your program.

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

unsigned int factorial(unsigned int numbers)
 {
    cout << "Entry to function #" << numbers << endl;
    if ( numbers > 0 )
    {
        cout << "This is a recursive function." << endl;
        return numbers * factorial( numbers-1 );
    }

    cout << "Exit from function #" << numbers << endl;
    return 1; // base case
 }

int main() 
{
    cout << "4! is " << factorial(4) << endl;
    return 0;
}    

If you stick the base case on the TOP, you'll see a familiar design.

unsigned int factorial(unsigned int numbers)
 {
    cout << "Entry to function #" << numbers << endl;

    if(numbers == 0)
    {
        cout << "Exit from function #" << numbers << endl;
        return 1; // base case
    }

    cout << "This is a recursive function." << endl;
    return numbers * factorial( numbers-1 );
 }

[glao]

Thank you all for the answers.

@AssertNull: I didn't know that with using the return..

But, if I don't use the return (in the void function) , I still can't understand the mechanism.How all the calls to exit from function occurs..And in the reverse order.

It seems like somehow they are kept in memory??

[Reverend Jim]

Each iteration means the another copy of the function is running until the last one exits.

That's not quite the case as I understand it. There is only one copy of the function. What happens is that with each call, values get pushed onto the stack (and get popped off when each call exits).

[AssertNull]

I had a post that disappeared. Let me try again. Not typing the whole thing out again, but I think it'll make the point.

And in the reverse order.

True, but I think it's better to think of the printouts being in NESTED order rather than REVERSE order. Consider your code. For a shorter post, I'll change the parameter from 4 to 2. Here's the function...

 void message(int numbers)
 {
    cout << "Entry to function #" << numbers << endl;
    if ( numbers > 0 )
    {
        cout << "This is a recursive function." << endl;
        message( numbers-1 );
        return;  // missing this line
    }
    cout << "Exit from function #" << numbers << endl;
 }

Printout (in order) - note the "nesting" (0 is inside 1, which is inside 2).

Entry to function # 2
This is a recursive function.
Entry to function # 1
This is a recursive function.
Entry to function # 0
Exit from function # 0
Exit from function # 1
Exit from function # 2

Let's change this to something NON-recursive.

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

void message0()
{
    cout << "Entry to function 0" << endl;
    cout << "Exit from function 0" << endl;
}

void message1()
{
    cout << "Entry to function 1" << endl;
    cout << "This is a recursive function." << endl;
    message0();
    cout << "Exit from function 1" << endl;
}

void message2()
{
    cout << "Entry to function 2" << endl;
    cout << "This is a recursive function." << endl;
    message1();
    cout << "Exit from function 2" << endl;
}

int main() 
{
    message2();
    return 0;
}    

Same printout, same code executed. Now INLINE the message0, message1, and message2 functions (that is, copy and paste them directly into the calling function's code). Same code, same printout, same order, but hopefully this time it's clear why the order is what it is.

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int main() 
{
    { // message2 function
        cout << "Entry to function 2" << endl;
        cout << "This is a recursive function." << endl;
        { // message1 function
            cout << "Entry to function 1" << endl;
            cout << "This is a recursive function." << endl;
            { // message0 function
                cout << "Entry to function 0" << endl;
                cout << "Exit from function 0" << endl;
            }
            cout << "Exit from function 1" << endl;
        }
        cout << "Exit from function 2" << endl;
    }
    return 0;
}

[rubberman]

Persuant to my comment about recursive exceptions, that tool found that a lot of C++ compilers in the early 1990's had major exception handling issues! I had written a solid recursive fib function in C years before for a contract I had with the Mellon Bank to balance their S&P 500 index funds daily after the market closed. It was used to determine which of the "smaller" equities would be included in the bag of stocks, so the appropriate buy/sell orders would be placed before the market open the following day.

At the time, they had over $50 billion in investments - retirement funds from states, major corporations, etc.

[glao]

Ok, thanks!
@AssertNull: It is more clear with the example.