Kotlin 递归(递归函数)和尾递归
-
递归函数定义:在 Kotlin 中,递归函数是指一个函数调用自身。递归通常用于解决可以分解为相似子问题的问题,例如计算阶乘。
-
避免无限递归:为了防止无限递归,通常使用条件语句(如
if...else
)来定义递归的结束条件,确保递归能够在某个点停止。 -
尾递归优化:Kotlin 支持尾递归优化,这通过在递归函数前使用
tailrec
修饰符实现。尾递归函数在最后一个操作是对自身的调用时有效,这样的优化可以避免栈溢出,使递归更加高效。
在 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) // 第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
修饰符标记函数。