Kotlin 的递归和 Java 的还是有比较大的不同，必须手动调用尾递归优化，而且还有比较严格的限制，如果不细致思考很容易优化失败。
要知道，手动尾递归优化成功的必要条件是：
- 使用
tailrec 标明函数为尾递归 - 在函数最后进行递归调用
这个“最后”并不仅仅指最后一条语句，而是特别要求执行顺序的最后。以最简单的递归求阶乘为例，直接求阶乘的代码为：
1
2
3
4
5
6
7
| fun factorial(n: Long): Long {
return if (n <= 1) {
n
} else {
n * factorial(n - 1)
}
}
|
注意：这个函数只是为了演示原理，实际最多只能求 25 的阶乘，实际应用中最好不要采取如上写法。
这时候，如果只是简单地在 fun 前面加上 tailrec 就会发现 Longellij IDEA 会有如下警告：
这是因为，函数最后一条语句执行时，要先计算 factorial(n - 1)，再将计算结果和 n 相乘，最后得出返回值，所以尾递归优化失败了。
实际上，正确的尾递归优化应该按照如下方式：
1
2
3
4
5
6
7
8
9
10
11
12
| fun factorial(n: Long): Long {
return fact(n)
}
tailrec fun fact(num: Long, accum: Long = 1): Long {
val soFar = num * accum
return if (num <= 1) {
soFar
} else {
fact(num - 1, soFar)
}
}
|
多加一个函数参数，就能简单地把乘法计算置于递归调用之前。
这里附上一份简单的测试代码，说明尾递归优化的实际运行情况：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| fun main(args: Array<String>) {
testFactorial("原始阶乘函数", ::normalFactorial)
testFactorial("失败的尾递归优化", ::tailFactorial)
testFactorial("正确的尾递归优化", ::factorial)
}
fun testFactorial(caseName: String, func: (Long) -> Long, times: Int = 10000, input: Long = 10000): Unit {
val start = System.currentTimeMillis()
for (i in 1..times) {
func(10000)
}
val end = System.currentTimeMillis()
val cost = end - start
println("$caseName 用时：$cost")
}
fun normalFactorial(n: Long): Long {
return if (n <= 1) {
n
} else {
normalFactorial(n - 1) * n
}
}
tailrec fun tailFactorial(n: Long): Long {
return if (n <= 1) {
n
} else {
tailFactorial(n - 1) * n
}
}
fun factorial(n: Long): Long {
return fact(n)
}
tailrec fun fact(num: Long, accum: Long = 1): Long {
val soFar = num * accum
return if (num <= 1) {
soFar
} else {
fact(num - 1, soFar)
}
}
|
最后，在我的机器上得到的结果是：
1
2
3
| 原始阶乘函数 用时：1181
失败的尾递归优化 用时：1175
正确的尾递归优化 用时：432
|
这样，就能明显看出尾递归优化的作用了。