以干草堆递归地查找针的索引。

我非常接近完成我的功能。我需要采取2个字符串，并返回字符串2中的字符串1的索引。我知道有一个查找功能，但我无法使用它。它也必须用递归编程来完成。以干草堆递归地查找针的索引。

我有以下几点。

int index_of(string haystack, string needle) { 

    int index = 0; 
    string test = haystack.substr(index, needle.length()); 

    if (test == needle) { 
     return index; 
    } 
    else { 
     return 1 + index_of(haystack.substr(1), needle); 
    } 

}

它返回干草堆里针的索引没有问题，但有2件事情需要做我不知道。

1）如果针不在干草堆中，则需要返回-1。如果它不存在，我已经完成了它，它返回-1，但因为它是递归的，所以它添加了其他时间返回1.我不知道如何在最后返回一个值而无需在其上添加所有其他实例。

2）我想在它内使用一个辅助函数，我不知道该怎么做。

感谢您的帮助！

来源

2015-11-01 Brandon Turpy

一般而言，您希望返回未掺杂的递归函数的值。在你的情况下，这样的：

return 1 + index_of(some_parameters);

应该是这样的：

return index_of(some_parameters);

现在，你只需要选择的参数，这样你可以跟踪指数的，直到你需要返回它，或者-1。

一个这样的功能可能具有构造：

index_of(string haystack, string needle, int index);

来源

2015-11-01 22:56:45

这里是一个示范项目，显示功能如何实现。

#include <iostream> 
#include <string> 

std::string::size_type index_of(std::string haystack, const std::string &needle) 
{ 
    if (haystack.size() < needle.size()) return std::string::npos; 

    if (haystack.compare(0, needle.size(), needle) == 0) return 0; 

    std::string::size_type index; 

    return (index = index_of(haystack.substr(1), needle)) == std::string::npos ? index : ++index; 
} 

int main() 
{ 
    std::string haystack("asdfghjkl"); 
    std::string needle("gh"); 

    std::string::size_type index = index_of(haystack, needle); 

    if (index != std::string::npos) 
    { 
     std::cout << "string \"" << needle 
        << "\" is found in string \"" << haystack 
        << "\" at position " << index 
        << std::endl; 
    } 
    else 
    { 
     std::cout << "string \"" << needle 
        << "\" is not found in string \"" << haystack << "\"" 
        << std::endl; 
    } 
}

它的输出是

string "gh" is found in string "asdfghjkl" at position 4

当然最简单的方法是定义一个静态变量，它会保持在源字符串中的当前位置。但在这种情况下，我不认为这样的函数是“纯粹的递归”。

来源

2015-11-01 23:41:26

以干草堆递归地查找针的索引。

回答

相关问题