Not able to generate correct output in recursive function?

Question

I'm trying to write a function that detects the number the negative integers in a stack recursively. Currently the snippet below is what I have, however it is not giving the correct answer so far. I tested with a stack of 11 elements with 7 negatives and got the output given below. There is definitely something wrong with the loop structure but I have not been able to pinpoint and fix it yet. Any help will be appreciated!

12356657235681623569772357137235729723574562357617235777623579372358096

My function below:

size_t r_func(stack<int> st1)
{   
    if(st1.size() == 0) return 0;
    int r = st1.top();
    st1.pop();
    cout << (r<0)+r_func(st1);
}

Your function doesn't return anything if st1.size() is nonzero, even though you declared it to return size_t. The numbers you're seeing is just random garbage from the stack. (Suggestion: always compile with compiler warnings on.) — Rufflewind
– Rufflewind, Commented Oct 12, 2014 at 0:15

Rufflewind · Accepted Answer · 2014-10-12 03:45:51Z

1

size_t r_func(stack<int> st1)
{   
    if(st1.size() == 0) return 0;
    int r = st1.top();
    st1.pop();
    cout << (r<0)+r_func(st1);
}

r_func is supposed to return a size_t, but if st1.size() is not zero then it won't return anything. The compiler should've given you a warning about this!

To correct this, add a line that returns the number of negative numbers in your stack:

    ...
    st1.pop();
    const size_t neg_count = (r < 0) + r_func(st1);
    cout << neg_count;
    return neg_count;
}

Edit: To write this tail-recursively, it's necessary to keep track of the size in an accumulator (here it's called neg_accum):

size_t r_func(stack<int> st1, size_t neg_accum = 0)
{   
    if (st1.size() == 0) {
        cout << neg_accum;
        return neg_accum;
    }
    int r = st1.top();
    st1.pop();
    return r_func(st1, (r < 0) + neg_accum);
}

edited Oct 12, 2014 at 3:45

answered Oct 12, 2014 at 0:23

Rufflewind

9,0362 gold badges41 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

sparta93 Over a year ago

After implementing the said changes, I got the output 12234556677 instead of 7. I used the same stack again for testing which has 7 negatives and a total of 11 elements.

Rufflewind Over a year ago

Well yes, I assumed that's what you wanted! If you put your cout inside the recursive function it will be called for every element. If you don't want that, you need to pull the cout outside as Daniel L suggested.

sparta93 Over a year ago

Ah yea, I should have not put the cout in there, but yes, I want the function to just give me the number of negatives in the stack. So for the above mentioned example, I want it to output 7. Also as Daniel L suggested, his method would work however I want the function to be directly called without the use of cout.

Rufflewind Over a year ago

Then you need to add a "wrapper" function that does the cout, or write it tail-recursively with an accumulator and call cout when the size reaches zero (which is really contrived because you may as well just use a while/for loop).

sparta93 Over a year ago

Sorry, I'm new to c++. How would I attempt to write it tail-recursively?

|

Daniel L · Accepted Answer · 2014-10-12 00:22:52Z

0

As Rufflewind said, you should replace 'cout <<' with 'return' and call your function in this way: 'cout << r_func(st1);'

answered Oct 12, 2014 at 0:22

Daniel L

1885 bronze badges

Collectives™ on Stack Overflow

Not able to generate correct output in recursive function?

2 Answers 2

9 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related