Kotlin 递归（递归函数）和尾递归

调用自身的函数称为递归函数。而这种技术称为递归。

一个物理世界的例子就是放置两面平行相对的镜子。它们之间的任何物体都会被递归地反射。

递归在编程中是如何工作的？

fun main(args: Array<String>) {
    ... .. ...
    recurse()
    ... .. ...
}

fun recurse() {
    ... .. ...
    recurse()
    ... .. ...
}

这里，recurse() 函数在其自身的函数体中被调用。这个程序是这样工作的：

在这里，递归调用会无限进行，导致无限递归。

为了避免无限递归，可以使用 if...else (或类似方法)，其中一个分支进行递归调用，另一个分支不进行。

示例：使用递归查找数字的阶乘

fun main(args: Array<String>) {
    val number = 4
    val result: Long

    result = factorial(number)
    println("Factorial of $number = $result")
}

fun factorial(n: Int): Long {
    return if (n == 1) n.toLong() else n*factorial(n-1)
}

运行程序后，输出将是

Factorial of 4 = 24

这个程序是如何工作的？

factorial() 函数的递归调用可以用下图解释：

涉及的步骤如下：

factorial(4)              // 1st function call. Argument: 4
4*factorial(3)            // 2nd function call. Argument: 3
4*(3*factorial(2))        // 3rd function call. Argument: 2
4*(3*(2*factorial(1)))    // 4th function call. Argument: 1 
4*(3*(2*1))                 
24

Kotlin 尾递归

尾递归是一个通用概念，而不是 Kotlin 语言的特性。一些编程语言（包括 Kotlin）使用它来优化递归调用，而其他语言（例如 Python）则不支持。

什么是尾递归？

在普通递归中，您首先执行所有递归调用，最后根据返回值计算结果（如上面的示例所示）。因此，在所有递归调用完成之前，您都无法得到结果。

在尾递归中，先进行计算，然后执行递归调用（递归调用将当前步骤的结果传递给下一个递归调用）。这使得递归调用等同于循环，并避免了堆栈溢出的风险。

尾递归的条件

如果一个递归函数对其自身的函数调用是其执行的最后一个操作，那么它就有资格进行尾递归。例如：

示例 1： 不符合尾递归，因为对自身的函数调用 n*factorial(n-1) 不是最后一个操作。

fun factorial(n: Int): Long {

    if (n == 1) {
        return n.toLong()
    } else {
        return n*factorial(n - 1)     
    }
}

示例 2： 符合尾递归，因为对自身的函数调用 fibonacci(n-1, a+b, a) 是最后一个操作。

fun fibonacci(n: Int, a: Long, b: Long): Long {
    return if (n == 0) b else fibonacci(n-1, a+b, a)
}

要在 Kotlin 中告诉编译器执行尾递归，您需要使用 tailrec 修饰符标记该函数。

示例：尾递归

import java.math.BigInteger

fun main(args: Array<String>) {
    val n = 100
    val first = BigInteger("0")
    val second = BigInteger("1")

    println(fibonacci(n, first, second))
}

tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
    return if (n == 0) a else fibonacci(n-1, b, a+b)
}

运行程序后，输出将是

354224848179261915075

此程序计算斐波那契数列的第 100 项。由于输出可能是非常大的整数，我们从 Java 标准库导入了 BigInteger 类。

这里，fibonacci() 函数被标记为 tailrec 修饰符，并且该函数符合尾递归调用。因此，编译器在这种情况下优化了递归。

如果您尝试在不使用尾递归的情况下查找斐波那契数列的第 20000 项（或其他大整数），编译器将抛出 java.lang.StackOverflowError 异常。然而，我们上面的程序工作正常。这是因为我们使用了尾递归，它使用高效的基于循环的版本而不是传统的递归。

示例：使用尾递归计算阶乘

上面示例中计算数字阶乘的示例（第一个示例）无法针对尾递归进行优化。下面是一个执行相同任务的程序。

fun main(args: Array<String>) {
    val number = 5
    println("Factorial of $number = ${factorial(number)}")
}

tailrec fun factorial(n: Int, run: Int = 1): Long {
    return if (n == 1) run.toLong() else factorial(n-1, run*n)
}

运行程序后，输出将是

Factorial of 5 = 120

编译器可以优化此程序中的递归，因为递归函数符合尾递归条件，并且我们使用了 tailrec 修饰符，它告诉编译器优化递归。