如何检测根递归调用？

Question

假设我们正在编写一个简单的递归函数 fib(n) 来计算第 n 个斐波那契数。现在，我们希望函数打印第 n 个数字。由于重复调用同一函数，因此必须存在一个条件，仅允许根调用进行打印。问题是：如何在不传递任何附加参数或使用全局/静态变量的情况下编写此条件。

所以，我们正在处理这样的事情：

int fib(int n) {
    if(n <= 0) return 0;
    int fn = 1;
    if(n > 2) fn = fib(n-2) + fib(n-1);
    if(???) cout << fn << endl;
    return fn;
}

int main() {
    fib(5);
    return 0;
}

我认为根调用与所有子调用不同，它返回到不同的调用者，即本例中的 main 方法。我想知道是否可以使用这个属性来编写条件以及如何使用。

更新：请注意，这是一个人为的示例，仅用于展示想法。从标签中应该可以清楚地看出这一点。我不是在寻找标准解决方案。谢谢。

Answer 1

我执行此操作的方法是使用辅助函数：

int _fib(int n) {
    if(n <= 0) return 0;
    int fn = 1;
    if(n > 2) fn = _fib(n-2) + _fib(n-1);
    return fn;
}

int fib(int n) {
    int fn=_fib(n);
    cout << fn << endl;
    return fn;
}

或者，您可以这样编写（c++）：

int fib(int n, bool f=true) {
    if(n <= 0) return 0;
    int fn = 1;
    if(n > 2) fn = fib(n-2, false) + fib(n-1, false);
    if(f) cout << fn << endl;
    return fn;
}

Answer 2

根递归调用是调用递归的点，即main中的调用。鉴于此，您可以稍微重写您的代码（如下所示）：

int fib(int n) {
    if(n <= 0) return 0;
    int fn = 1;
    if(n > 2) fn = fib(n-2) + fib(n-1);
    return fn;
}

int main() {
    cout << fib(5) << endl;
    return 0;
}

Answer 3

如果您确实想问 C 是否可以访问某种 API，允许函数体中的代码找出调用执行函数的位置，那么答案是否。

Answer 4

这里有一个棘手的方法，尽管我不确定这是否值得:)：

int fib(int n) {
//    if(n <= 0) return 0;
    int isRoot;
    if ( n <= 0 ){
        isRoot = 1;
        n = -n;
    }
    else isRoot = 0;
    int fn = 1;
    if(n > 2) fn = fib(n-2) + fib(n-1);
    if(isRoot) cout << fn << endl;
    return fn;
}

int main() {
    fib(-5);
    return 0;
}

但是，该函数要求您不要真正发送负值:)。

Answer 5

我认为您可以从堆栈中获取返回地址，并以某种方式将其与 fib 函数的地址进行比较。返回地址应该位于接近参数 n 的地方，除非 n 在某个寄存器中传递，但在标准 C 中不应该。您只需知道返回地址相对于参数的位置即可。