C++递归问题<confused>

Question

我正在努力理解递归,我想我已经好了......我正在尝试构建一个搜索函数(比如std :: string.find()),它搜索给定字符串中的另一个字符串,例如:

给(大)字符串:"ru the running cat"

搜索(小)字符串:"运行"

我正在尝试返回我正在搜索的单词的索引(在上面的情况下它将是**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_"它仍然停留在''(空间) - >我怎么能让它'重置' s指针？

Answer 1

1. 不要更改任何状态变量. 您的代码不应包含++ 任何位置的运算符.您不是试图循环数据结构并以某种方式更改本地变量 - 您每次都试图生成一个全新但更小的问题.因此,所有这些++运算符 - 无论是前增量还是后增量 - 都是红旗.

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

   让我们系统地看一下.

   假设你有一个工作index_of,你只想用比你短的输入来调用它,并且干草堆和针都不是空的.那么两件事之一可能是:

   • 干草堆以与针相同的字母开头,你只需要看一点就可以验证这一点.
     - 验证成功后会发生什么 - 如果失败怎么办？这是一个index_of子问题吗？

   • ...或者干草堆开始出错,你需要更深入地看.
     - 正在深入研究干草堆的index_of子问题？

   请注意,如果haystack 启动 OK,并不一定意味着它以完整的搜索字符串开头 - 如果它启动正常但不是以完整的搜索字符串开头,那么您实际上不需要继续查找.这意味着"启动"子问题与子问题的索引根本不同:

   • index_of:这里,无法在索引0处找到搜索字符串意味着您需要进一步查看.
   • starts_with:在这里,无法在索引0处找到搜索字符串意味着您需要停止.

   这是可能的说startswith(haystack, needle):= 0==index_of(haystack, needle),但显然index_of是一个比较复杂的问题,更昂贵的解决方案-所以你不应该这样做; 起初它也更令人困惑.

3. 确定您的基本情况 - 当针头或干草堆是空的时,这意味着什么？

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

摘要

我不打算为你解决你自己的谜题,但回顾一些提示......

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