c++递归函数的问题

Question

我有一个简短的递归函数要写，当我通过g++运行它时，我的函数有一个返回segfault 11的问题。我不擅长递归，才刚刚开始学习。如果你有任何建议，请告诉我!目标是计算有多少节点的值大于输入值"m"。

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
}

Answer 1

你的评论在撒谎。

// smaller case
Node *Bane = h;

在这里，您将Bane设置为传递给函数的相同值。你实际上不是测试列表中的下一个项目，你是在做同样的列表。

这不是代码中唯一的问题，但它至少可以帮助解决您提出的问题。

Answer 2

关于递归的第一个问题应该总是:我需要递归吗?当迭代LinkedList的元素时，绝对不需要递归。

其次，我强烈建议不要使用自己的链表类，因为编写自己的链表类所花费的时间最好花在学习诸如STL之类的库上，这些库可以免费提供出色的数据结构(其他同事也能理解!)。

然而，要完成您试图递归实现的目标，您可以将"答案"放入类成员，全局变量(颤音)或将答案传递给函数的每次调用(在第一个实例中传递零)，但我不能强调递归方法不是解决此问题的正确方法。首先，answer变量在LinkedList类中没有位置，全局变量几乎总是邪恶的，传递一个你只是增加的值是低效和令人困惑的。

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

下面是一个使用简单LinkedList类的更好的非递归实现:

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