3

在递归调用中检索函数顺序的最简单方法是什么。例如，如果我们有一个递归函数，它会一直调用自己，直到找到基本情况，然后一次返回一个函数。返回的第一个函数的顺序为 0，第二个函数的返回顺序为 1，依此类推...检索订单信息的简单方法是什么？比如说，当它是三阶功能时，我想做一些特别的事情。

编辑：我希望堆栈顶部的函数为零。

Edit2：我要解决的问题是返回按顺序遍历二叉树的第 n 个元素。

4

3 回答 3

5

如果您从一个看起来像这样的递归函数开始

void recursive(int p1, String p2, long p3) {
    ...
    if (someCondition) {
        recursive(nextP1, nextP2, nextP3);
    }
}

将其更改为：

void recursive(int p1, String p2, long p3, int level) {
    ...
    if (someCondition) {
        recursive(nextP1, nextP2, nextP3, level+1);
    }
}

现在通过调用从零开始

recursive(initialP1, initialP2, initialP3, 0);

level将显示recursive您上面的调用次数。

编辑：（顶部为零）

您还可以转换函数以返回其级别以实现“顶部为零”策略：

int recursive(int p1, String p2, long p3) {
    if (baseCase) {
        return 0;
    }
    ...
    int level = 0;
    if (someCondition) {
        level = 1+recursive(nextP1, nextP2, nextP3);
    }
    return level;
}

请注意，在这种情况下，level直到最后一次递归调用返回后，您才能找到您的。

于 2012-09-14T22:26:36.580 回答
3

dasblink 为您提供的案例与您建议的实施方式相反，因为随着递归的深入，级别计数器会上升（增量）。

如果您希望它随着递归的深入而减少，这意味着您事先知道确切的递归深度。

在大多数情况下，如果您知道确切的递归深度，您将不会使用递归，您将使用循环（for、while、repeat/until 等）。事实上，在这种情况下使用递归并不是最优的，因为递归堆栈被分配（更高的内存消耗）并且循环效率更高。

于 2012-09-14T22:36:35.517 回答
0

  • 如果级别 0 应该是最后一次“嵌套调用”，那么它通常是类似于停止问题的不可判定问题，因为您不能只说“在 3 次嵌套调用之后，函数将返回一个值”。只有通过模拟特定函数的计算才能向前看。

  • 如果 level 0 应该是第一次调用，那么它非常简单，您可以使用 level 作为方法的参数并递增它。

顺便说一句，有趣的问题，请参阅http://en.wikipedia.org/wiki/Halting_problem

于 2012-09-14T22:35:35.197 回答