CODEWITHSUNDEEP
c++recursion
Jarrod
Jarrod

Reputation: 1705

Value not retained when returning from recursive stack frames?

I'm just beginning to learn recursion and I'm stuck on a problem which involves finding the number of cannonballs in a pile of cannonballs with each level obviously being a square number eg. the top stack is 1, the second is 4, the third is 16 and so on...

The stack of cannonballs looks conceptually like this

I've traced the steps in Xcode watching the variable's values and what I'm seeing is that when the base case is reached the 'numBalls' is correct but when the stack frames end, the value is not returned and is lost.

I feel like I should know how to fix this, but I can't seem to figure it out.

Here is the code I'm using:

#include <iostream>
using namespace std;

int GetCannonballs(int height, int numBalls);
int Cannonballs(int height);

int main(int argc, char *argv[]) {
    cout << Cannonballs(3) << endl;
}

int GetCannonballs(int height, int numBalls)
{
    if(height <= 0) {
        return numBalls;
    } else {
        return GetCannonballs(height-1, numBalls + (height*height));
    }
}

int Cannonballs(int height) // Wrapper function
{
    int numBalls = 0;
    GetCannonballs(height, 0);
    return numBalls;
}

The return value I get is 0.

Any help or explanation of my error or misunderstanding would be very appreciated!

Thank you.

Upvotes: 1

Views: 207

Answers (2)

Seth Carnegie
Seth Carnegie

Reputation: 75150

In

int numBalls = 0;
GetCannonballs(height, 0);
return numBalls;

You forget to set numBalls to the result of GetCannonballs. You need to do

int numBalls = 0;
numBalls = GetCannonballs(height, 0);
return numBalls;

Or more succinctly,

return GetCannonballs(height, 0);

Note that you can get rid of the wrapper function by using default arguments for GetCannonballs:

int GetCannonballs(int height, int numBalls = 0);

Congratulations on writing a proper tail-recursive function by the way.

Upvotes: 5

Moon
Moon

Reputation: 35305

Change:

int Cannonballs(int height) // Wrapper function
{
    int numBalls = 0;
    GetCannonballs(height, 0);
    return numBalls;
}

To:

int Cannonballs(int height) // Wrapper function
{
    return GetCannonballs(height, 0);
}

Upvotes: 1

Related Questions