Issue with recursive function C++

Question

I have a short recursive function to write, and I am having an issue with my function returning seg fault 11 when I run it through g++. I am pretty bad at recursion, and just starting to learn it. Please let me know if you have any suggestions! The goal is to count how many nodes have a value larger than the inputed value "m" .Here is my code:

int LinkedList::countOccurrencesMoreThanRec(int m)
{
    // first do the base cases that do not require recursion
    if (head == NULL)
        return -1;
    int answer = 0;
    if ((head -> getNext()) == NULL)
    {
        if ((head -> getValue()) > m)
            answer ++;
        return answer;
    }
    // if none of those were true, call the recursive helper method
    Node *BatMan = head;
    answer = countOccurrencesMoreThan(BatMan, m);
    return answer;
}

/* countOccurrencesMoreThan
 *
 * private recursive method.  
 * TODO: fill in this method
 */

int LinkedList::countOccurrencesMoreThan(Node *h, int m)
{
    // check for the base case(s)
    int answer = 0;
    if ((h -> getNext()) == NULL)
    {
        if ((h -> getValue()) > m)
            answer++;
        return answer;
    }
    // smaller case
    Node *Bane = h;
    answer = countOccurrencesMoreThan(Bane, m);
    return answer;
    // general case
}

And yes I know this is much easier without recursion, but I need to do it with recursion — user3330905
– user3330905, Commented May 21, 2014 at 0:46
in countOccurences, is it guaranteed that the parameter h is not null? maybe if ((h -> getNext()) == NULL) condition causes segfault when h is null. — Varaquilex
– Varaquilex, Commented May 21, 2014 at 0:48
I believe I tested in the second one to make sure it was not null — user3330905
– user3330905, Commented May 21, 2014 at 0:58

Greg Hewgill · Accepted Answer · 2014-05-21 00:48:20Z

1

Your comments are lying.

// smaller case
Node *Bane = h;

Here, you're setting Bane to the same value that was passed in to your function. You're not actually testing the next item in the list, you're doing the same list again.

This isn't the only problem in your code, but it will at least help with the question you asked.

answered May 21, 2014 at 0:48

Greg Hewgill

1.0m192 gold badges1.2k silver badges1.3k bronze badges

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

2 Comments

user3330905 Over a year ago

When i fixed that, I end up with my program saying that it only finds one value of each number I test, regardless of how many are in my linked list. Any ideas on that?

Greg Hewgill Over a year ago

Yup, that's the other problem I noticed. You'll have to significantly change your program logic to fix that; notice that the only time you ever change the value of answer is when you're looking at the last item in your list.

Matt Coubrough · Accepted Answer · 2014-05-21 02:07:15Z

One of the first questions with recursion should always be, do I need recursion? When iterating elements of a LinkedList there is absolutely no need to recurse.

Secondly, I strongly advise against rolling your own linked list class as the time it takes to write your own would be better spent learning libraries such as the STL which give you great data structures out of the box for free (that other colleagues understand!).

However to accomplish what you are trying to achieve recursively, you could either make the "answer" int a class member, a global variable (shudder) or pass the answer to each invocation of the function (passing zero in the first instance), but I cannot stress enough that the recursive approach is not the right approach for this problem. The answer variable has no place in a LinkedList class for a start, global variables are almost always evil, and passing around a value you're simply incrementing is inefficient and confusing.

int LinkedList::countOccurrencesMoreThan(Node *h, int m, int answer)
{

    if( h->getValue() > m ) {
        ++answer;
    }
    if (h -> getNext() == NULL)
    {
       return answer;
    }
    countOccurrencesMoreThan( h->getNext(), m, answer);

}

Here is a better non recursive implementation with a simple LinkedList class:

void LinkedList::countOccurrencesMoreThan(int value) {

    Node* node = this->head;
    int occurrences = 0;
    while(node != NULL) {
        if( node->getValue() > v ) {
            ++occurrences;
        }
        node = node->getNext();
    }
    std::cout << "occurrences = " << occurrences << std::endl;
}

Collectives™ on Stack Overflow

Issue with recursive function C++

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related