跳到主要内容

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

提示

  1. 递归函数定义：在 Kotlin 中，递归函数是指一个函数调用自身。递归通常用于解决可以分解为相似子问题的问题，例如计算阶乘。

  2. 避免无限递归：为了防止无限递归，通常使用条件语句（如 if...else）来定义递归的结束条件，确保递归能够在某个点停止。

  3. 尾递归优化：Kotlin 支持尾递归优化，这通过在递归函数前使用 tailrec 修饰符实现。尾递归函数在最后一个操作是对自身的调用时有效，这样的优化可以避免栈溢出，使递归更加高效。

在 Kotlin 中，一个调用自身的 函数 被称为递归函数，这种技术被称为递归。

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

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

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

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

在这里，recurse() 函数从它自己的函数体内被调用。这个程序的工作方式如下：

Kotlin 中递归函数调用 在这里，递归调用永远持续下去，导致无限递归。

为了避免无限递归，可以使用 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() 函数的递归调用可以在下图中解释：

Kotlin 中递归是如何工作的？ 这里涉及的步骤是：

factorial(4)              // 第1次函数调用，参数：4
4*factorial(3)            // 第2次函数调用，参数：3
4*(3*factorial(2))        // 第3次函数调用，参数：2
4*(3*(2*factorial(1)))    // 第4次函数调用，参数：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 修饰符告诉编译器优化递归。

最后于 更新