C++ 堆栈溢出异常，可能是由于递归

Question

我有一些代码可以正常工作。但是，有时我的程序由于错误而不得不关闭。我曾尝试调试此错误，但在执行此操作时遇到了几个问题。

当我在 debug 中运行时，在启动程序后很快就会出现堆栈溢出错误，这比在 release 中出现错误要快得多。

我已经缩小了在调试中抛出错误的时间点，即第 3570 次调用此递归函数时。

void setRankAbove(vector<nodeStructure> &allNodes, int index, int rankToSet) {
    if (rankToSet>=allNodes[index].rank) {
        allNodes[index].rank = rankToSet;
        if (allNodes[index].root != index) {
            setRankAbove(allNodes, allNodes[index].parent, rankToSet + 1,debug);
        }           
    }
}

关于为什么程序在这里崩溃以及为什么它只在调试时崩溃的任何想法？

无论如何，回到最初的问题，我已经缩小了失败的地方。

vector<vector<double>> backwardsAggregation(int inputRows, int inputCols, vector<vector<double>> &localCostsStepOne, vector<nodeStructure> &nodeMST,float sigma,bool debug) {
    // create 2D array of local costs step 2
    vector<double> localOneDim(inputCols);
    vector<vector<double>> localCostsRootToLeaf(inputRows, localOneDim);

    // factors defined in paper
    double nodeFactor = (1 - exp(-1 / (sigma*sigma)));
    double parentFactor = exp((double)(-0.5) / (sigma*sigma));
    cout << "Step 3.2.1" << endl;
    try{
        aggregateStepTwo(nodeMST, nodeMST[0].root, localCostsStepOne, localCostsRootToLeaf, parentFactor, nodeFactor, debug, 0);
    }
    catch (const std::exception & ex) {
        cout<< "exception"<< endl;
        cout << ex.what() << endl;
    }

    cout << "Step 3.2.2" << endl;
    return localCostsRootToLeaf;
}

在调用一定次数后调用 aggregateStepTwo 时失败。它可能会递归调用它 1,000,000 次。这是另一个堆栈溢出吗？

如果是这样，我该如何摆脱堆栈溢出？

谢谢罗布

Answer 1

你有尾递归。用迭代算法代替这种递归通常非常简单。这是一种天真的方法，它只是将递归重写为无限循环，在递归停止的相同位置中断。

void setRankAbove(vector<nodeStructure> &allNodes, int index, int rankToSet) {
  while (1) {
    if (rankToSet < allNodes[index].rank) {
      break;
    }
    allNodes[index].rank = rankToSet;
    if (allNodes[index].root == index) {
      break;
    }
    index = allNodes[index].parent;
    rankToSet++;
  }
}

这应该有效。

现在，如果您不喜欢 break，可以从以下观察中获得更“优雅”的解决方案(有争议):

1. 在第一次迭代中，分配仅取决于 index
的值
2. 每个后续迭代都取决于 index 的根以及涉及 index 的父级和 rank+1 的关系。

所以第一个看起来像一个特例。其他依赖于涉及 index 和 index 的父级的相同表达式。因此，如果我们将第一种情况排除在循环之外，我们将得到以下算法:

void setRankAbove(vector<nodeStructure> &allNodes, int index, int rankToSet) {
  if (rankToSet < allNodes[index].rank) {
    return;
  }

  allNodes[index].rank = rankToSet++;
  int parent = allNodes[index].parent;

  while (allNodes[index].root != index && rankToSet >= allNodes[parent].rank) {
    index = parent;
    allNodes[index].rank = rankToSet++;
    parent = allNodes[index].parent;
  }
}

我真的很惊讶编译器没有自动将这个递归转换成一个循环。您是否没有使用优化标志进行编译，还是我对编译器的期望过高？