StackOverflowException在非無限遞歸字符串搜索中

Question

背景。 我的腳本在遞歸搜索大字符串中的特定文本時遇到StackOverflowException。循環不是無限的;在9,000-10,000個合法搜索之間出現問題（對於特定搜索） - 我需要繼續。我使用尾遞歸（我認爲），這可能是我的問題的一部分，因爲我收集C＃不這樣做。但是，我不確定如何避免在我的情況下使用尾遞歸。

Question（s）。爲什麼會發生StackOverflowException？我的整體方法是否有意義？如果設計很糟糕，我寧願從那裏開始，而不僅僅是避免一個例外。但是，如果設計是可以接受的，我可以做些什麼關於StackOverflowException？

代碼。 我寫的這個類在大量文本（大約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。

很難說，因爲沒有顯示完整的實現，但基於我可以看到你或多或少正在編寫一個迭代器，但是你沒有爲一個（即IEnumerable）使用C＃構造。

我的猜測是「迭代器塊」可以讓你使這個算法更容易編寫，更容易非遞歸編寫，並且從調用者側更有效。

這裏是一個高層次看，你會如何構建這種方法，迭代器塊：

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(); 
} 

Answer 2

它似乎並不像遞歸這裏是正確的解決方案。通常在遞歸問題中，你有一些狀態傳遞給遞歸步驟。在這種情況下，你真的有一個簡單的while循環。下面我把你的方法體放在一個循環中，並將遞歸步驟更改爲continue。看看是否有效...

public string NextInstance() 
{ 
    while (true) 
    { 
     // 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()) 
      { 
       continue; // Start searching again... 
      } 
      // 
      else 
      { 
       return this.CurrentContext; 
      } 
     } 
     // No more instances of the primary search string 
     else 
     { 
      return null; 
     } 
    } 
}