1

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

要将标记字符串更改为关联的新标记字符串，我使用此向量查找函数

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

3 回答 3

3

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

于 2012-08-29T09:13:52.407 回答
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++;
    }
}
于 2012-08-29T09:19:57.850 回答
0

感谢您的评论和评论。

这些函数很好——这个递归函数包要求字符串存在于它所作用的数据库中，并且在这些错误识别特殊条件并插入一个虚拟字符之前，字符串检查。在这两个函数之前有一个递归函数——我没有正确地看到我已经编写了三个递归函数的捆绑包——并且其中一个正在参数中搜索比数据库中存在的字符串更长的字符串；显然参数比堆栈宽。检查参数，其中一个没有更新，也没有控制。

我修复了特殊条件，字符串现在长度相同并且搜索参数是固定的。

发布的功能并不太复杂。

于 2012-08-29T22:31:07.830 回答