我了解尾递归,但是我被分配编写代码来查看第 N 个斐波那契数是什么。 首先,这段代码确实有效。这不是最好的方法,但它是一种方法——但是我开始担心它不是尾递归。代码在这里:
static int fib_tail_helper(int n, int result) {
if (n == 0) {
return result;
}
else if (result == 0) {
return fib_tail_helper(n - 1, result + 1);
}
else {
return fib_tail_helper(n - 1, result + fib_tail_helper(n - 1, 0));
}
}
int fib_tail(int n) {
/*
// REQUIRES: n >= 0
// EFFECTS: computes the Nth Fibonacci number
// fib(0) = 0
// fib(1) = 1
// fib(n) = fib(n-1) + fib(n-2) for (n>1).
// MUST be tail recursive
*/
return fib_tail_helper(n, 0);
}
我最担心的是“return fib_tail_helper(n - 1, result + fib_tail_helper(n - 1), 0”。 我觉得好像会使用另一个堆栈,因此是非尾递归的......任何人都可以提供一些输入吗?
谢谢!!
最佳答案
不,它不是尾递归。
编译器需要首先评估 fib_tail_helper
参数,这意味着它将在继续调用最后一个 fib_tail_helper
作为返回值之前创建 n-1 个调用堆栈。
关于c++ - 在 Return 中调用自身两次——尾递归与否?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25943541/