這個遞歸程序堆棧溢出錯誤？ - C++

我是第一個C++類中的編程學生，最近我們給了一個任務來實現遞歸程序，該程序在給定字符串中查找給定子字符串的第一個匹配項。這個遞歸程序堆棧溢出錯誤？ - C++

例如：

int StringIndex("Mississippi", "sip"); // this would return 6

我們給出是使用遞歸輔助函數，它的索引作爲參數的提示。

以下是我迄今所做的：

int index_of(string s, string t) 
{ 
    int index = 0; 

    if (s[index] == NULL) 
     return -1; 
    else if (starts_with(s, t, ++index)) 
    { 
     return index; 
    } 
    return index_of(s, t); 
} 

bool starts_with(string s, string t, int index) 
{ 
    if (t[index] != s[index] || s[index] == NULL) 
     return false; 
    return starts_with(s, t, ++index); 
}

我得到一個堆棧溢出錯誤，我不明白爲什麼。那麼有人會幫助我理解爲什麼我會得到這個錯誤？並幫助我指出如何解決它的正確方向？

來源

2010-02-21 Alex

嘗試使用調試程序逐步運行例程，或者如果您不想陷入調試程序，請在函數的各個位置放置printf（）調用。然後運行你的程序，把輸出重定向到一個文件，當它崩潰後，從文件內容中檢查文件的內容......你將能夠看到你的程序正在做什麼，這將變得清楚爲什麼它無限遞歸併溢出堆棧。 – 2010-02-21 20:20:49

在編寫遞歸函數時，應始終記住兩件事：您需要停止遞歸的條件，並且每次函數調用都必須更接近停止條件。如果你沒有檢查停止條件，或者你的函數在每次調用期間沒有接近停止條件，你會遇到堆棧溢出（或無限循環）。

第一個函數的問題在於它沒有接近停止條件。最後你「在不改變s或t的情況下返回index_of（s，t）」。因此，函數將重複使用相同的參數，一次又一次，直到遇到堆棧溢出。

另一個問題是在你的starts_with函數中。它只會返回false，但從來不會。

來源

2010-02-21 19:48:01 stmax

當你說：

s[index] == NULL

你應該知道，C++的std ::字符串不必是空值終止內部 - 使用字符串的size()成員函數，而不是相反。另外，你正在通過值來傳遞字符串，這對於長字符串來說可能會迅速吃掉堆棧空間和動態內存。將它們作爲常量引用來代替：

bool starts_with(const string & s, const & string t, int index) 
{ 
    ... 
}

最後，正如其他人指出，只有功能之一，在這種情況下starts_with()應該是遞歸的。實際上，index_of()似乎毫無意義。

來源

2010-02-21 19:32:22

另外，條件't [index]！= s [index] || s [index] == NULL'應該顛倒過來，否則在檢查邊界之前你會檢查邊界。 – Thomas 2010-02-21 19:34:13

int index_of(string s, string t) 
{ 
    ... 

    // Your are calling yourself without modifying the 
    // input parameters. If you get here once, you'll 
    // never break out. 
    return index_of(s, t); 
}

沒有什麼變化s或t所以這可能永遠不會停止。

來源

2010-02-21 19:34:23

也++指數沒有多大意義。實際上，index_of中的整個變量沒什麼意義.. – falstro 2010-02-21 19:37:19

A）「starts_with」永遠不會返回true。所以你永遠不會退出index_of遞歸。
B）index_of對於遞歸沒有做任何事情，它只是用相同的信息再次調用自己。

基本上2上面的問題導致無限循環。您經常檢查相同的信息，並且沒有退出該循環的可能性。

來源

2010-02-21 19:55:28 Goz

如果你會原諒他指出，有些人可能認爲只是有點太可愛了錯誤的方式，考慮的區別：

See this answer

和：

如果你不」 t瞭解see this answer

來源

2010-02-21 20:38:58

偏離主題，但我很好奇：在提交答案之前，您怎麼知道鏈接會是什麼？它看起來不像你編輯修補它。 – Dan 2010-02-21 20:56:55

@丹：其實我編輯過它。據我所知，如果您在幾秒鐘內編輯，它不會將其顯示爲編輯。 – 2010-02-21 21:07:19

投票贊成既是有效的（如果有點混淆）答案，*和*一個公案。 – DSimon 2011-07-02 08:02:32

這個遞歸程序堆棧溢出錯誤？ - C++

回答

相關問題