Kotlin - 函数被标记为尾递归但未找到尾调用
我有一个用递归计算斐波那契数列的函数。
fun fibonacciRecursive(n: Long): Long {
if (n <= 1) {
return n
}
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}
它可以工作，但是如果数字很大，则需要很长时间才能执行。我听说 kotlin 有一个关键字 tailrec 可以改进递归并将函数重写为循环。 但是当我将这个关键字添加到这个函数时，编译器告诉一个函数被标记为尾递归，但没有找到尾调用。为什么我无法添加 tailrec？
I have a function that calculates the Fibonacci series with recursion.
fun fibonacciRecursive(n: Long): Long {
if (n <= 1) {
return n
}
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}
It works, but if the number is big then it takes a long time to execute. I've heard that kotlin has a keyword tailrec which improves the recursion and rewrites the function as a loop.
But when I add this keyword to this function, the compiler tells A function is marked as tail-recursive but no tail calls are found. Why I can't add tailrec?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
尾递归是一种递归类型，在每一层递归调用后不需要进行任何计算 - 它只是调用更深层次的杠杆，最深层次的结果是整个堆栈的结果的通话。
本质上，您可以忘记每个中间级别，当您到达“底部”时，只需获取结果并立即将其提供给原始调用者即可。
在你的情况下，你必须调用下一个级别，等待它，然后另一个，等待它，然后求和 - 这意味着你没有尾递归实现，因为你必须在中间级别之后做一些事情递归调用。
斐波那契数列（与所有递归解决方案一样）可以使用常规循环迭代求解，不需要大型调用堆栈，而大型调用堆栈最终也会减慢您的速度。尝试该实现将是一个很好的实践，尽管根据定义，该序列“很难”计算并且很快需要多次迭代。这也可以给你一个关于如何将其重写为尾递归的提示：
这里我们不需要“返回”来完成我们的计算。因此，在尾递归的实现中，您需要传递 x_n 和 x_n+x_n-1，而不是仅传递迭代索引，因此在最终级别您将已经获得总和 - 无需“返回”。尾递归本质上是可以轻松转换为循环的递归。
Tail recursion is a type of recursion where at each level no calculation needs to be done after the recursive call - it just calls the deeper lever, and the result at the deepest level is the result of the entire stack of calls.
In essence, you can forget about each intermediate level, and when you get to the "bottom", just take the result and give it immediately to the original caller.
In your case, you have to call the next level, wait for it, then another, wait for it, then sum it - that means you do not have a tail-recursion implementation since you have to do something in the intermediate levels after the recursive calls.
The Fibonacci sequence (as all recursive solutions) can be solved iteratively with a regular loop that does not require a large call stack that will eventually also slow you down. It would be good practice to try that implementation, though by definition this sequence is "hard" to compute and quickly requires many iterations. This can also give you a hint on how to re-write it as a tail recursion:
Here we don't need to "go back" to finish our calculation. So in your implementation of a tail recursion instead of passing only the iteration index, you need to pass x_n and x_n+x_n-1, so at the final level you will already have the sum - no need to "go back". Tail recursion is essentially recursion that can easily be transformed to a loop.
如果您想使用尾递归，通常需要相应地编写算法。对于斐波那契数列，将其转换为尾递归函数的最简单方法可能是向上计算而不是向下计算：（
不幸的是，我对 Kotlin 不了解，所以下面的代码是 Common Lisp 中的）。
正如您所看到的，在 fibo-slow 中，尾部位置是加法 (+)，而不是对递归函数的调用。
If you want to use tail-recursion, you usually need to write your algorithm accordingly. In case of Fibonacci, probably the easiest way to turn it into a tail recursive function is to calculate upwards instead of downwards:
(Unfortunately I have no idea about Kotlin, so code below is in Common Lisp).
As you can see, in
fibo-slow, the tail position is the addition (+), not the call to the recursive function(s).