CODEWITHSUNDEEP
c++loopsrecursion
sparta93
sparta93

Reputation: 3854

Not able to generate correct output in recursive function?

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

Upvotes: 0

Views: 76

Answers (2)

Rufflewind
Rufflewind

Reputation: 8956

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

Upvotes: 1

Daniel L
Daniel L

Reputation: 178

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

Upvotes: 0

Related Questions