----《第一季Kotlin崛起：次世代Android開發(fā) 》學習筆記
總目錄：每天學一點 Kotlin ---- 目錄
上一篇：每天學一點 Kotlin -- 函數(shù)：字面量
下一篇：每天學一點 Kotlin -- 函數(shù)：標準庫函數(shù)
1. 尾遞歸函數(shù)
1.1 遞歸函數(shù)：當特定的目標沒有完成時，函數(shù)一直在自己調(diào)用自己。
1.2 但是遞歸也有弊端琼稻，就是在完成最后一次遞歸前會占用大量的資源和內(nèi)存焚挠。所以遞歸用的較少。而且能用遞歸實現(xiàn)的功能蔬充，用循環(huán)肯定也能實現(xiàn)亭罪。
1.3 如果一個遞歸函數(shù)的調(diào)用可以簡化到使用一個特殊函數(shù)作為最后一次操作弧蝇，且調(diào)用的結(jié)果是一個返回值歧沪，那么系統(tǒng)就不會保持上一次操作的內(nèi)存堆棧歹撒。因此就不需要其他臨時變量來維持進一步操作，直接返回這個特殊函數(shù)調(diào)用的值即可诊胞。這種技術(shù)被稱為尾遞歸暖夭。運用尾遞歸可以寫出高效的遞歸算法，從而避免堆棧溢出錯誤 ---- 尾遞歸是對遞歸的優(yōu)化撵孤。
1.4 要在 Kotlin 中使用一個尾遞歸函數(shù)鳞尔，可以用 tailrec 關(guān)鍵字定義函數(shù)。如此早直，編譯器便可以確信每一次遞歸使用這個函數(shù)作為最后一次操作寥假。
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)
}
打印結(jié)果：
普通的遞歸：
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
可以看出，兩個函數(shù)計算的結(jié)果是一樣的霞扬，區(qū)別在于：
---- 普通的遞歸中糕韧，參數(shù)全部被保存下來，知道最后一層調(diào)用中計算得到結(jié)果后喻圃，再依次倒退和參數(shù)相加得到最終的結(jié)果
---- 在尾遞歸中萤彩，在 var re = tailFact2(m - 1, m + n) 這一行代碼中，每次向下調(diào)用自身時都已經(jīng)計算出結(jié)果了斧拍，直接把本次的結(jié)果向下計算雀扶，不需要保存之前的入?yún)?shù)了。
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)
}
打印結(jié)果：
普通的遞歸：start: 1634804071403
普通的遞歸：result = 165580141
普通的遞歸：end: 1634804071740
使用尾遞歸的遞歸: start: 1634804071740
使用尾遞歸的遞歸：result = 165580141
使用尾遞歸的遞歸: end: 1634804071740
可以看出肆汹，尾遞歸相比較與普通的遞歸愚墓，優(yōu)化效果還是很明顯的。
