静态编程语言-将函数标记为尾递归但未找到尾调用

Question

我有一个用递归计算斐波那契级数的函数。

fun fibonacciRecursive(n: Long): Long {
    if (n <= 1) {
        return n
    }

    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}

这是可行的，但如果数字很大，那么执行起来需要很长时间。我听说kotlin有一个关键字tailrec，它改进了递归并将函数重写为循环。但是当我将这个关键字添加到这个函数中时，编译器告诉我们，一个函数被标记为尾部递归，但没有找到尾部调用。为什么我不能添加tailrec？

Answer 1

如果要使用尾部递归，通常需要相应地编写算法。对于斐波那契函数，将其转换为尾部递归函数的最简单方法可能是向上计算，而不是向下计算：

（不幸的是，我不知道Kotlin，所以下面的代码是公共Lisp）。

(defun fibo-slow (n)
  "The classic, non- tail recursive way..."
  (if (<= n 1)
      n
      (+ (fibo-slow (- n 1))
         (fibo-slow (- n 2)))))

(defun up (n i-1 i-2 i)
  "Tail recursive 'kernel', passing the history as arguments."
  (if (= i n)
      (+ i-1 i-2)
      (up n (+ i-1 i-2) i-1 (+ i 1))))

(defun fibo-up (n)
  "The adapter for function up, so the interface remains the same as 'fibo-slow'."
  (case n
    (0 0)
    (1 1)
    (otherwise 
     (up n 0 1 1))))

如您所见，在fibo-slow中，尾部位置是加法（），而不是对递归函数的调用。

Answer 2

尾部递归是一种递归类型，在每个级别上，递归调用后不需要进行任何计算-它只调用更深层的杠杆，最深层的结果是整个调用堆栈的结果。

本质上，您可以忘记每个中间级别，当您到达“底部”时，只需获取结果并立即将其提供给原始调用方。

在你的例子中，你必须调用下一个级别，等待它，然后是另一个，等待它，然后求和——这意味着你没有尾递归实现，因为你必须在递归调用后的中间级别做一些事情。

斐波那契序列（与所有递归解一样）可以用一个规则循环迭代求解，该循环不需要大的调用堆栈，最终也会减慢速度。尝试这种实现是一种很好的做法，尽管根据定义，这个序列“很难”计算，并且很快需要多次迭代。这还可以提示您如何将其重新编写为尾部递归：

1. 每次迭代n给定x\u n和x\u n-1，设置x\u n-1=x\u n，x\u n=x\u n x\u n-1（或类似的东西）
2. 这样做直到达到所需的迭代量，在那里立即得到最终的总和

在这里，我们不需要“返回”来完成计算。因此，在尾部递归的实现中，而不是只传递迭代索引，您需要传递x\n和x\n x\n-1，因此在最后一级，您已经有了总和-无需“返回”。尾部递归本质上是可以轻松转换为循环的递归。