CODEWITHSUNDEEP
c++recursionlinked-list
user3330905
user3330905

Reputation: 15

Issue with recursive function C++

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
}

Upvotes: 0

Views: 267

Answers (2)

Matt Coubrough
Matt Coubrough

Reputation: 3829

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

Upvotes: 0

Greg Hewgill
Greg Hewgill

Reputation: 994659

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.

Upvotes: 1

Related Questions