c# - 非无限递归字符串搜索中的 StackOverflowException

Question

背景。我的脚本在递归搜索大字符串中的特定文本时遇到 StackOverflowException。循环不是无限的；问题发生在 9,000-10,000 次合法搜索之间(对于特定搜索)——我需要它继续进行。我正在使用尾递归(我认为)，这可能是我的问题的一部分，因为我认为 C# 做得不好。但是，我不确定在我的案例中如何避免使用尾递归。

问题。 为什么会发生 StackOverflowException？我的总体方法是否有意义？如果设计很糟糕，我宁愿从那里开始，而不是仅仅避免异常。但是如果设计是可以接受的，我能对 StackOverflowException 做些什么呢？

代码。我编写的类(class)在大量文本(约 6MB)中搜索联系人(来自指定列表的约 500 多个)。我使用的策略是搜索姓氏，然后在姓氏前后不久的某处查找名字。我需要在给定文本中找到每个联系人的每个实例。 StringSearcher 类有一个递归方法，可以继续搜索联系人，只要找到一个就返回结果，但会跟踪它在搜索时停止的位置。

我按以下方式使用这个类:

StringSearcher searcher = new StringSearcher(
    File.ReadAllText(FilePath),
    "lastname",
    "firstname",
    30
);

string searchResult = null;
while ((searchResult = searcher.NextInstance()) != null)
{
    // do something with each searchResult
}

总的来说，脚本似乎有效。大多数联系人返回我期望的结果。但是，当主要搜索字符串非常常见(数千次命中)而次要搜索字符串从不或很少出现时，问题似乎会发生。我知道它不会卡住，因为 CurrentIndex 正在正常推进。

这就是我所说的递归方法。

public string NextInstance()
{
    // Advance this.CurrentIndex to the next location of the primary search string
    this.SearchForNext();

    // Look a little before and after the primary search string
    this.CurrentContext = this.GetContextAtCurrentIndex();

    // Primary search string found?
    if (this.AnotherInstanceFound)
    {
        // If there is a valid secondary search string, is that found near the
        // primary search string? If not, look for the next instance of the primary
        // search string
        if (!string.IsNullOrEmpty(this.SecondarySearchString) &&
            !this.IsSecondaryFoundInContext())
        {
            return this.NextInstance();
        }
        // 
        else
        {
            return this.CurrentContext;
        }
    }
    // No more instances of the primary search string
    else
    {
        return null;
    }
}

StackOverflowException 在以下方法中的 this.CurrentIndex = ... 上发生:

private void SearchForNext()
{
    // If we've already searched once, 
    // increment the current index before searching further.
    if (0 != this.CurrentIndex)
    {
        this.CurrentIndex++;
        this.NumberOfSearches++;
    }

    this.CurrentIndex = this.Source.IndexOf(
            this.PrimarySearchString,
            ValidIndex(this.CurrentIndex),
            StringComparison.OrdinalIgnoreCase
    );

    this.AnotherInstanceFound = !(this.CurrentIndex >= 0) ? false : true;
}

如果需要，我可以包含更多代码。如果其中一个方法或变量有问题，请告诉我。

*性能并不是真正的问题，因为这可能会作为计划任务在晚上运行。

Answer 1

你有一个 1MB 的堆栈。当堆栈空间用完而您仍然需要更多堆栈空间时，将抛出 StackOverflowException。这可能是也可能不是无限递归的结果，运行时不知道。无限递归只是一种使用更多可用堆栈空间的有效方法(通过使用无限量)。您可以使用有限的数量，恰好超过可用数量，您将得到相同的异常。

虽然还有其他方法可以耗尽大量堆栈空间，但递归是最有效的方法之一。每种方法都根据该方法的签名和局部变量添加更多空间。深度递归会占用大量堆栈空间，因此如果您希望深度超过几百级(甚至很多)，您可能不应该使用递归。请注意，任何使用递归的代码都可以迭代编写，或者使用显式 Stack。

很难说，因为没有显示完整的实现，但根据我所看到的，您或多或少正在编写一个迭代器，但您没有使用 C# 构造(即 IEnumerable )。

我的猜测是“迭代器 block ”将使您能够使该算法更易于编写，更易于非递归编写，并且从调用方的角度来看更有效。

下面是关于如何将此方法构造为迭代器 block 的高级 View :

public static IEnumerable<string> SearchString(string text
    , string firstString, string secondString, int unknown)
{
    int lastIndexFound = text.IndexOf(firstString);

    while (lastIndexFound >= 0)
    {
        if (secondStringNearFirst(text, firstString, secondString, lastIndexFound))
        {
            yield return lastIndexFound.ToString();
        }
    }
}

private static bool secondStringNearFirst(string text
    , string firstString, string secondString, int lastIndexFound)
{
    throw new NotImplementedException();
}