C++ 递归问题

Question

我正在努力理解递归，我想我已经明白了......我正在尝试构建一个搜索函数(如 std::string.find())，用于在给定字符串中搜索另一个字符串例如:

Given (big) string: "ru the running cat"

search (small) string: "run"

我正在尝试为我正在搜索的单词返回索引(在上面的情况下它将是 **7)我拥有的递归方法如下 - 我似乎无法得到它正确返回索引。

调用递归函数:

index = index_of(imput.c_str(), search.c_str())

递归方法:

int index_of( const char * i, const char * s) {
 int j;
 if (*s == '\0') { return; }
 if (*i == '\0') {
  return NULL;
 }
 else if ( *i == *s ) {
  index_of((i++), (s++));
 }
 else {
  j += index_of((i++), s);
 }
 return j;
}

另一个可预见的问题是，当(就像在示例中一样 - 好吧，它很糟糕，但我需要一个可以工作的)它到达“ru_”时它仍然停留在''(SPACE)上 ->我如何将它带到'重置's 指针？

Answer 1

1. 不要更改任何状态变量。您的代码不应在任何地方 包含运算符++。您不是在尝试遍历数据结构并以某种方式更改局部变量——您是在尝试每次生成一个全新但较小的问题。因此，所有这些 ++ 运算符 - 无论是前增量还是后增量 - 都是危险信号。

2. 您有多个子问题。(...所以单函数递归并不理想)。

   让我们系统地看一下。

   假设您有一个有效的 index_of 并且您只想使用比您的输入更短的输入来调用它，并且 haystack 和 needle 都不是空的。那么两件事之一可能是:

   • 大海捞针开头的字母是一样的，你只需要看得更深一点就可以验证这一点。
     - 如果验证成功怎么办 - 如果失败怎么办？这是一个 index_of 子问题吗？

   • ...或者大海捞针一开始就错了，您需要更深入地了解。
     - 深入研究大海捞针是一个 index_of 子问题吗？

   请注意，如果 haystack 开始 OK 并不一定意味着它以完整搜索字符串开始 - 如果它开始 OK 但不是 从完整的搜索字符串开始，您真的不需要继续寻找。这意味着“starts-with”子问题与 index-of 子问题根本不同:

   • index_of:在这里，在索引 0 处找不到搜索字符串意味着您需要进一步查找。
   • starts_with:此处，在索引 0 处找不到搜索字符串意味着您需要停止。

   说 startswith(haystack, needle):= 0==index_of(haystack, needle) 是可能的，但显然 index_of是一个更昂贵的解决方案的更复杂的问题 - 所以你不应该那样做;一开始也比较困惑。

3. 确定您的基本情况 - 当针或大海捞针为空时，这意味着什么？

4. 好名字有助于澄清事情，递归在最好的时候也很难阅读 - 例如 Yacoby 的回复在这里有一些有意义的选择。

总结

我不会为你解开你自己的谜题，但有一些小窍门......

• 避免更改您的局部变量:您试图定义一个子问题，然后只为那些更新、更短的参数调用正确的函数。不要使用副作用，它们会使事情变得非常复杂。
• 递归不一定意味着只有一个函数 A 调用 A - 它可以是任何最终终止的循环调用图；你可以使用更多的功能
• 如果 needle 和 haystack 以相同的字母开头，那并不意味着整个 needle 都在 haystack 的开头——如果不是，您仍然需要继续搜索
• 这一行是错误的:if (*s == '\0') { return 1; }