如何检测根递归调用？

假设我们正在编写一个简单的递归函数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; 
}

我认为根本的呼叫通过返回到不同的来电者，即本例中的主要方法，从所有的孩子不同。我想知道是否有可能使用此属性来编写条件和方式。

更新：请注意，这是一个人为设计的例子，仅用于介绍该想法。这应该从标签中清楚。我不寻找标准的解决方案。谢谢。

来源

2010-04-22 Ahmed Abdelkader

正如许多答案中指出的那样，创建一个启动递归的包装函数是很常见的做法。自定义之前/之后处理（如IO）可以去那里。 – 2010-04-22 16:18:45

我会做到这一点的方法是使用一个辅助功能：

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; 
}

来源

2010-04-22 16:13:04 Blindy

不错的一个。我暂时忘了默认参数。 – 2010-04-22 16:17:36

顺便说一句，你的第一个解决方案不是打印一切吗？似乎函数_fib应该调用它自己，而不是fib。 – Feyyaz 2010-04-22 16:33:03

呃yea，小错字：p – Blindy 2010-04-22 16:58:32

根递归调用是递归被调用的点，即在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; 
}

来源

2010-04-22 16:08:08 fbrereto

又来了一个取巧的办法，虽然我不知道这是值得的:)：

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; 
}

但是，在函数要求你不要真的意味着发送一个负值:)。

来源

2010-04-22 16:08:24 Feyyaz

如果你真的要问清楚是否ç可以访问某种类型的API，它允许函数体中的代码从执行函数的调用中找出答案，答案是no。

来源

2010-04-22 16:18:36 reinierpost

没问题，但是*你*（和程序员一样）可以装饰呼叫以找出它们来自哪里。 – Blindy 2010-04-22 16:20:13

其他答案已经涵盖了。 – reinierpost 2010-04-23 10:12:57

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

来源

2010-04-22 17:06:57

如何检测根递归调用？

回答

相关问题