----《第一季Kotlin崛起：次世代Android开发 》学习笔记
总目录：每天学一点 Kotlin ---- 目录
上一篇：每天学一点 Kotlin -- 函数：字面量
下一篇：每天学一点 Kotlin -- 函数：标准库函数
1. 尾递归函数
1.1 递归函数：当特定的目标没有完成时，函数一直在自己调用自己。
1.2 但是递归也有弊端，就是在完成最后一次递归前会占用大量的资源和内存。所以递归用的较少。而且能用递归实现的功能，用循环肯定也能实现。
1.3 如果一个递归函数的调用可以简化到使用一个特殊函数作为最后一次操作，且调用的结果是一个返回值，那么系统就不会保持上一次操作的内存堆栈。因此就不需要其他临时变量来维持进一步操作，直接返回这个特殊函数调用的值即可。这种技术被称为尾递归。运用尾递归可以写出高效的递归算法，从而避免堆栈溢出错误 ---- 尾递归是对递归的优化。
1.4 要在 Kotlin 中使用一个尾递归函数，可以用 tailrec 关键字定义函数。如此，编译器便可以确信每一次递归使用这个函数作为最后一次操作。
1.5 举个栗子1：
fun main() {
println(fact(5))
println(fact2(5))
}
fun fact(k: Int): Int {
println("k = " + k)
if (k == 1) {
return 1
} else {
var re = k * fact(k - 1)
println("re = " + re)
return re
}
}
fun fact2(k: Int): Int {
fun tailFact2(m: Int, n: Int): Int {
println("m = " + m + ", n = " + n)
if (m == 1) {
return n
} else {
var re = tailFact2(m - 1, m + n)
println("re = " + re)
return re
}
}
return tailFact2(k, 1)
}
打印结果：
普通的递归：
k = 5
k = 4
k = 3
k = 2
k = 1
re = 2
re = 6
re = 24
re = 120
120
使用尾递归的递归:
m = 5, n = 1
m = 4, n = 6
m = 3, n = 10
m = 2, n = 13
m = 1, n = 15
re = 15
re = 15
re = 15
re = 15
15
可以看出，两个函数计算的结果是一样的，区别在于：
---- 普通的递归中，参数全部被保存下来，知道最后一层调用中计算得到结果后，再依次倒退和参数相加得到最终的结果
---- 在尾递归中，在 var re = tailFact2(m - 1, m + n) 这一行代码中，每次向下调用自身时都已经计算出结果了，直接把本次的结果向下计算，不需要保存之前的入参参数了。
1.6 举个栗子2：
fun main(args: Array<String>){
println("普通的递归：start: " + System.currentTimeMillis())
println("普通的递归：result = " + fibo(40))
println("普通的递归：end: " + System.currentTimeMillis())
println("使用尾递归的递归: start: " + System.currentTimeMillis())
println("使用尾递归的递归：result = " + fibo2(40))
println("使用尾递归的递归: end: " + System.currentTimeMillis())
}
// 之前的递归
fun fibo(startNum: Int): Int = when(startNum){
0 -> 1
1 -> 1
else -> fibo(startNum - 1) + fibo(startNum - 2)
}
// 使用尾递归
fun fibo2(startNum: Int): Int{
tailrec fun fiboTail(index: Int, ant: Int, act: Int): Int =
when(index){
0 -> ant
else -> fiboTail(index - 1, act, ant + act)
}
return fiboTail(startNum, 1, 1)
}
打印结果：
普通的递归：start: 1634804071403
普通的递归：result = 165580141
普通的递归：end: 1634804071740
使用尾递归的递归: start: 1634804071740
使用尾递归的递归：result = 165580141
使用尾递归的递归: end: 1634804071740
可以看出，尾递归相比较与普通的递归，优化效果还是很明显的。
网友评论