c++ - 递归调用溢出

Question

在测试数据集上，以下代码有效，但当我更改为具有相似大小的第二个测试集时，它会溢出。

要将一串标记更改为关联的新标记串，我使用了这个 vector 查找函数

//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

调用堆栈是一种有限的资源，可以像其他任何资源一样耗尽。您的函数越大(相对于您在其中创建的局部变量的创建)，每次调用在堆栈上使用的空间量就越大。这是递归不可避免的事情，除非您可以通过某种方式限制递归调用的次数。