C++递归问题<混淆>

1. 不要更改任何状态变量。 您的代码不应包括操作员 ++ 在任何地方 . 您并没有试图循环一个数据结构,并以某种方式更改局部变量——您每次都试图生成一个全新但较小的问题。所以,所有这些 ++ 运算符-无论是前增量还是后增量-都是红色标志。

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

   让我们系统地看看这个。

   假设你有工作 index_of 你只想用比你的短的输入来调用它,而且草垛和针还没有空出来。那么两件事之一可能是:

   • 干草堆从和针相同的字母开始,你只需要看得更深一点来验证这一点。
     -如果验证成功会发生什么-如果失败会怎样?这是一个 索引 子问题?

   • …或者干草堆开始出错了,你需要看得更深。
     -深入研究干草堆是子问题的索引吗?

   注意如果干草堆 开始 好吧,这并不一定意味着它从 满的 搜索字符串-如果它开始正常但确实 不 从完整的搜索字符串开始,您真的不需要继续查找。这意味着“从”子问题与子问题的索引有根本不同:

   • 索引的 :这里,在索引0处找不到搜索字符串意味着您需要进一步查找。
   • 以…开头 :这里,在索引0处找不到搜索字符串意味着您需要停止。

   它是 可能的 说 startswith(haystack, needle):= 0==index_of(haystack, needle) 但很明显 索引的 对于更昂贵的解决方案来说,这是一个更复杂的问题——所以您不应该这样做;一开始它也更令人困惑。

3. 确定基本案例 -当针或干草堆都是空的,这意味着什么?

4. 好的名字有助于澄清问题,而且在最好的时候递归很难阅读——例如,yacoby的回复在这里有一些有意义的选择。

总结

我不打算为你解决你自己的难题,但在扼要重述中的一些技巧…

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

我就是这样做的,这就是通过将它转换成不同的函数来简化一切。未经测试,但希望能给你一个想法。

/**
 * Checks if one string starts with another string. This returns an
 * incorrect result if it is called where prefix is an empty string.
 */
bool starts_with_impl(const char* haystack, const char* prefix) {
    if ( *prefix == 0 ){ 
        //reached the end of prefix without having found a difference in characters
        return true;
    }else if ( *haystack == 0 || *prefix != *haystack ){
        //either prefix is longer than haystack or there is a difference in characters.
        return false;
    }
    //move along the haystack and prefix by one character
    return starts_with_impl(++haystack, ++prefix);
}
/**
 * Wrapper around starts_with_impl that returns false if prefix is an empty string
 */
bool starts_with(const char* haystack, const char* prefix) {
    return *prefix ? starts_with_impl(haystack, prefix) : false;
}

int get_substr_impl(const char* haystack, const char* const needle, int index) {
    if ( *haystack == 0 ){
        //reached the end of haystack with no match, -1 is no string found
        return -1;
    }else if ( starts_with(haystack, needle) ){
        //we have found a substring match.
        return index;
    }
    //move along haystack by one character
    return get_substr_impl(++haystack, needle, ++index);
}
/**
 * Wrapper function for the above to hide the fact we need an additional argument.
 * I am avoiding using a default argument as it makes a messy api
 */
int get_substr(const char* haystack, const char* const needle) {
    return get_substr_impl(haystack, needle, 0);
}

从评论中

在get-substr-impl方法中有2个常量……

故意的。

// means that the data is constant, in other words I can't change the value of needle
const char* needle;

//means that as well as the data being constant 
//I can't change the address that the pointer points to.
const char* const needle;

从主方法中,我不会用get-substr中给出的相同参数来调用teh-get-substr-impl吗?

我把它拆分为 get_substr_impl 有一个附加(必需)参数 int index 这是函数内部工作所必需的,应始终从0开始。你可以打电话 get_substr_impl("abc", "a", 0); ,看起来更好,打电话更容易理解 get_substr("abc", "a"); 它可以避免错误(比如 get_substr_impl("abc", "a", 1); )

首先,你有两个 i 在你的代码中。甚至不应该编译。

也, index_of((i++), (s++)); 实际上与以下内容相同:

index_of(i, s); 
++i;
++s;

换句话说,您使用与第一次调用索引时相同的参数调用over&over的索引。(它永远不会返回到++i)。

另外,纯粹是风格化的,但是由于返回类型是int,所以应该返回0,并保存空值以用于指针。

这里的主要问题是您使用的是后增量,并且(i++)的结果是i。你必须使用++i