在链接列表中找到值的递归方法

Question

template<class Type>
int StringList<Type>::find(Type value)
{
int count = 0;
// Start of linked list
Node<Type> *current = head;
// Traverse list until end (NULL)
while (current != NULL)
{
    // Increase counter if found
    if (current->data == value)
    {
        count++;
    }
    // If not, move to the next node
    current = current->next;
}
cout << value << " was found " << count << " times" << endl;
return 0;


// same function but using Recursive method


// Start of linked list
Node<Type> *current = head;
int count = 0;
// Thinking this is the base case, since its similar to the while loop
if (current == NULL)
{
    return 0;
}
// same as the while loop, finding the value increase the count, or in this case just prints to console
if ((current->data == value))
{
    cout << "Found match" << endl;
    return 0;
}
else
{   // If it didnt find a match, move the list forward and call the function again
    current = current->next;
    return find(value);
}
}

该功能应该找到所搜索的值并返回链接列表中某些值的次数。

如何将第一个使用while循环的方法变成做同样但使用递归的东西？

Answer 1

对于启动器而不是返回类型int，最好使用像size_t

这样的无符号类型

您可以使用以下方法。定义两种方法。第一个是公共非静态方法find定义为

template<class Type>
size_t StringList<Type>::find( const Type &value ) const
{
    return find( head, value );
}

第二个是一种私有静态方法，其定义了两个参数，例如

template<class Type>
static size_t StringList<Type>::find( Node<Type> *current, const Type &value )
{
    return current == nullptr ? 0 : ( current->data == value ) + find( current->next, value );
}

Answer 2

要使用递归，您将需要更改查找功能的签名(或与其他签名添加新功能(以将节点指针作为参数：

template<class Type>
int StringList<Type>::find(Type value, Node<Type> *where)
{
    if (where != nullptr)
    {
    // Do things
    }
}

然后，当您穿越列表时，您将where->next传递到该功能。一旦您以nullptr值击中列表的末尾，堆栈即将展开。

递归的关键方面，因为所使用的功能或方法仅需处理容器的单个节点。然后，它将其称为下一个节点要处理，直到没有更多的节点为止。为了使此工作，该功能需要节点作为参数处理，这是您当前代码遇到问题的地方。

请记住，递归的优雅和简单性不是免费的。方法对自己进行的每个呼叫都会吞噬堆栈，因此，如果您的流程堆栈耗尽，则足够大的容器可能会导致崩溃。

Answer 3

我如何将第一个使用一个while循环的方法变成 做同样的事情但使用递归的东西？

以下内容将更接近您想要的东西。您确实应该提供一个[MCVE] ...缺乏迫使您对代码的许多猜测和假设。

// It looks like StringList is a class (I ignored template issues), 
// and it appears that your class holds 'anchors' such as head
//   StringList is probably the public interface.
//   
// To find and count a targetValue, the code starts 
//   at the head node, and recurses through the node list.
// I would make the following a public method.
//
int StringList::findAndCountTargetValue(int targetValue)
   {
      int retVal = 0;
      if (nullptr != head)          // exists elements to search?
         retVal = head->countTV(targetValue); // recurse the nodes
      // else no match is possible
      return(retVal);
   }

// visit each node in the list 
int Node::countTV(const int targetValue)
   {
      int retVal = 0;  // init the count
      if (data != targetValue)  // no match
      {
         if(nullptr != next)            // more elements?
            retVal += next->countTV()   // continue recursive count
      }
      else
      {
         std::cout << "Found match" << std::endl;   // for diag only
         retVal += 1; // because 1 match has been found
         if(nullptr != next)           // more elments
            retVal += next->countTV(); // continue recursive count
      }
      return (retVal);  // always return value from each level
   }