我正在努力理解递归,我想我已经明白了......我正在尝试构建一个搜索函数(如 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 指针?
最佳答案
- 不要更改任何状态变量。您的代码不应在任何地方 包含运算符
++
。您不是在尝试遍历数据结构并以某种方式更改局部变量——您是在尝试每次生成一个全新但较小的问题。因此,所有这些++
运算符 - 无论是前增量还是后增量 - 都是危险信号。 您有多个子问题。(...所以单函数递归并不理想)。
让我们系统地看一下。
假设您有一个有效的
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
是一个更昂贵的解决方案的更复杂的问题 - 所以你不应该那样做;一开始也比较困惑。确定您的基本情况 - 当针或大海捞针为空时,这意味着什么?
好名字有助于澄清事情,递归在最好的时候也很难阅读 - 例如 Yacoby 的回复在这里有一些有意义的选择。
总结
我不会为你解开你自己的谜题,但有一些小窍门......
- 避免更改您的局部变量:您试图定义一个子问题,然后只为那些更新、更短的参数调用正确的函数。不要使用副作用,它们会使事情变得非常复杂。
- 递归不一定意味着只有一个函数
A
调用A
- 它可以是任何最终终止的循环调用图;你可以使用更多的功能 - 如果 needle 和 haystack 以相同的字母开头,那并不意味着整个 needle 都在 haystack 的开头——如果不是,您仍然需要继续搜索
- 这一行是错误的:
if (*s == '\0') { return 1; }
关于C++ 递归问题 <confused>,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2252996/