遞歸調用溢出

Question

在測試數據集下面的代碼工作，但是當我改變爲第二測試集與一個同樣大小溢出。

要更改標記的字符串轉換爲標記相關的新的字符串，我用這個矢量查找功能

//looks for input string in vector and returns output, 'c' is check row, 'r' is return row 
string vectorSearch(string &check, int &direction, int n, int c, int r, int level) 
{ 
    if ((direction == 1 && check.length() <= 1) || n == list.size()-1 ||(direction == 0 && check.length() > 1)) { //if reading and string is 1 char then pass over 
     if (direction == 1){ //convert '???' into '?' 
      string temp = ""; 
      bool wildToken = false; 
      for (unsigned int i = 0; i < check.length(); i++) { 
       temp+='?'; 
       if (check.compare(temp) == 0) { check = '?'; wildToken = false; } //done,'???" case, return '?' token 
       else if (check[i] == '?') wildToken = true; //not done searching 
      } 
     } 

     return check; 
    } else { 
     if (list[n][c] == check || list[n][c] == ('0'+check)) //add dummy '0' 
      return list[n][r]; 
     else 
      return vectorSearch (check, direction, n+1, c, r, level); 
    } 
} 

工作正常了十轉換堆棧後溢出

vectorSearch從該函數調用

//this function takes an ontology and direction==1 (default) changes from string 
//to single char or if direction==0 takes single char and converts to string representation 
string Lexicon::convertOntology(string input, int level, int direction, string out, string temp) 
{ 
    if (input == "" && temp == "") 
     return out; //check for completed conversion 
    else { 
     if (direction == 0 || input[0] == '.' || input[0] == '-' || input == "") { //found deliniator or end 
      if (temp == "") temp = input[0]; //condition for reverse w/o deleniators 
      if (input != "") return convertOntology(input.substr(1), level+1, direction, 
       out+=vectorSearch(temp, direction, 0, direction, 1-direction, level)); 
      else { 
       string empty = ""; 
       return convertOntology(empty, level+1, direction, out+=vectorSearch(temp, direction, 0, direction, 1-direction, level)); 
      } 
     } else 
      return convertOntology(input.substr(1), level, direction, out, temp+=input[0]); //increment and check 
    } 
} 

Answer 1

感謝您的評論和意見。

的功能是細 - 此遞歸函數束需要在字符串中它起作用的數據庫中存在，並且這些前的字符串檢查錯誤地識別的特殊條件和插入虛擬炭。在這兩個之前有一個遞歸函數 - 我沒有正確地看到我寫了一個三個遞歸函數 - 一個是在參數中搜索一個比數據庫中存在的字符串更長的字符串;顯然參數比堆棧寬。檢查了參數，其中一個沒有更新並且沒有控制。

我固定在特殊的情況下，字符串現在是相同的長度和搜索參數是固定的。

發佈的功能不是太複雜。

Answer 2

調用堆棧是一個有限的資源，可以像任何其他一樣耗盡。你的函數越大（相對於你在其中創建的局部變量的創建而言），每個調用在堆棧上使用的空間量越大。除非你能以某種方式限制遞歸調用的次數，否則這是遞歸不可避免的。

Answer 3

你只能去用遞歸如此之深運行的堆棧空間之前。幸運的是，任何遞歸函數都可以重寫爲迭代。我相信下面是你的vectorSearch的一個正確的迭代實現，我將把後者留給你。

string vectorSearch(string &check, int &direction, int n, int c, int r, int level) 
{ 
    while(true) 
    { 
     if ((direction == 1 && check.length() <= 1) || n == list.size()-1 ||(direction == 0 && check.length() > 1)) { //if reading and string is 1 char then pass over 
      if (direction == 1){ //convert '???' into '?' 
       string temp = ""; 
       bool wildToken = false; 
       for (unsigned int i = 0; i < check.length(); i++) { 
        temp+='?'; 
        if (check.compare(temp) == 0) { check = '?'; wildToken = false; } //done,'???" case, return '?' token 
        else if (check[i] == '?') wildToken = true; //not done searching 
       } 
      } 

      return check; 
     } else if (list[n][c] == check || list[n][c] == ('0'+check)) {//add dummy '0' 
       return list[n][r]; 
     } 

     n++; 
    } 
}