Scala 尾部递归

递归是一种将问题分解成更小的子问题并为每个问题调用自己的方法。也就是说，它简单地说就是函数调用自己。 尾部递归函数 比非尾部递归函数更好，因为尾部递归可以被编译器优化。如果一个递归函数的递归调用是该函数所做的最后一件事，则该函数被称为尾部递归。没有必要保留之前的状态记录。

对于尾部递归函数，程序中会使用 导入scala.annotation.tailrec 包。

语法

@tailrec
def FunctionName(Parameter1, Parameter2, ...): type = …

让我们通过例子来理解尾部递归。

例子:

// Scala program of GCD using recursion
import scala.annotation.tailrec
 
// Creating object
object GFG
{
    // Function defined
    def GCD(n: Int, m: Int): Int =
    {
        // tail recursion function defined
        @tailrec def gcd(x:Int, y:Int): Int=
        {
            if (y == 0) x
            else gcd(y, x % y)
        }
        gcd(n, m)
    }
     
    // Main method
    def main(args:Array[String])
    {
        println(GCD(12, 18))
    }
}

输出

6

正如我们在上面的例子中看到的，@tailrec用于gcd函数，这是一个尾部递归函数。通过使用尾部递归，不需要保留gcd函数的前一个状态的记录。

例子:

// Scala program of factorial using tail recursion
import scala.annotation.tailrec
   
// Creating object
object GFG
{
    // Function defined
    def factorial(n: Int): Int =
    {
        // Using tail recursion
        @tailrec def factorialAcc(acc: Int, n: Int): Int =
        {
            if (n <= 1)
                acc
            else
                factorialAcc(n * acc, n - 1)
        }
        factorialAcc(1, n)
    }
       
    // Main method
    def main(args:Array[String])
    {
        println(factorial(5))
    }
}

输出

120

在上面的代码中，我们可以使用@tailrec注解来确认我们的算法是尾部递归的。如果我们使用这个注解，而我们的算法不是尾部递归的，编译器会抱怨。例如，如果我们试图在上面的阶乘方法的例子中使用这个注解，我们会得到下面的编译时错误。

例子:

// Scala program of factorial with tail recursion
import scala.annotation.tailrec
   
// Creating object
object GFG
{
    // Function defined
    @tailrec def factorial(n: Int): Int =
    {
        if (n == 1)
            1
        else
            n * factorial(n - 1)
    }
       
    // Main method
    def main(args:Array[String])
    {
        println(factorial(5))
    }
}

输出

无法优化@tailrec注解的方法factorial：它包含一个不在尾部位置的递归调用。