[TOC] ### Kotlin相比于Java | 相比于java | 描述??????????????????| | ------- | ------------------- | | 新增 | 支持對尾遞歸函數的優化，提高代碼性能 | ### 遞歸函數 遞歸函數指的是在函數體內部調用函數本身。遞歸函數可以用少量的代碼實現需要多次重復計算的程序。 ``` fun sum(num: Int): Int { //定義一個sum()函數 if (num == 1) { //當變量num為1時，則指定返回值為1 return 1 } else { return num + sum(num - 1) //當變量num不為1時，則返回num與函數sum()返回值之和 } } fun main(args: Array<String>) { println(sum(4)) //調用遞歸函數 } ``` 運行結果 ``` 10 ``` 在上述代碼中，首先定義了一個sum()函數，該函數是用于求1～4的數字之和，如果傳遞到該函數中的參數為1時，該函數會返回1，如果傳遞到該函數中的參數不為1時，則返回參數num與函數sum()返回值之和。由于在第6行代碼中調用了函數本身，因此這個sum()函數是一個普通的遞歸函數。由于方法的遞歸調用過程比較復雜，接下來我們通過一個圖例來分析整個調用過程，如圖所示  ### 尾遞歸函數 我們首先說遞歸函數，什么是遞歸函數呢？**遞歸函數指在方法體內部還去調用了函數本身，就是遞歸**。 那什么又是尾遞歸函數呢？尾遞歸是一種特殊的遞歸函數。**當遞歸調用是整個函數體中最后執行的語句的時候，這個遞歸就是尾遞歸**。 尾遞歸函數的特點是在遞歸過程中不用做任何操作，當編譯器檢測到一個函數調用是尾遞歸函數時，它就覆蓋當前的活動記錄而不是在棧中去創建一個新的。因為遞歸調用是當前活躍期內最后一條待執行語句，于是當調用返回時棧中沒有其他事情可做，因此也就沒有保存的必要。這樣可以大大縮減所使用的棧空間，使得程序運行效率變得更高。**雖然編譯器能夠優化尾遞歸造成的棧溢出問題，但是在編程中還是應該盡量避免尾遞歸的使用**。 尾遞歸函數是一種特殊的遞歸函數，特殊之處在于該函數的調用出現在函數的末尾。通**常情況下，尾遞歸函數一般用在連續求和、連續求差等程序中。** 我們舉例說明，比如我們對某一個數字進行累加計算，我們**先用普通的遞歸函數實現**，參考代碼： ~~~ fun main(args: Array<String>) { println(oddAdd(100)) } var count = 0 fun oddAdd(num: Int): Int { println("計算機第${++count}計算") return if (num == 1) { 1 } else { //這里是遞歸，不是尾遞歸，除了調用oddAdd方法，還有加法操作 num + oddAdd(num - 1) } } ~~~ 運行結果 ``` ....... 計算機第95計算 計算機第96計算 計算機第97計算 計算機第98計算 計算機第99計算 計算機第100計算 5050 Process finished with exit code 0 ``` 針對**以上代碼的遞歸只是普通遞歸，因為代碼的第21行，除了調用函數本身，還執行了一個“+”操作**。 我們把上面累加操作**改成尾遞歸的形式**，參考代碼： ~~~ fun main(args: Array<String>) { println(oddAdd(100)) } var count = 0 fun oddAdd(num: Int, total: Int = 0): Int { println("計算機第${++count}計算") return if (num == 1) { 1 + total } else { //這里尾遞歸，遞歸調用時整個函數中最后執行的語句的時候 oddAdd(num - 1, num + total) } } ~~~ 運行結果 ``` ........ 計算機第97計算 計算機第98計算 計算機第99計算 計算機第100計算 5050 Process finished with exit code 0 ``` #### 尾遞歸函數的優化 **遞歸的時候，容易出現的問題就是內存溢出**。比如我們直接對“100000”就會出現內存溢出，參考代碼： ~~~ fun main(args: Array<String>) { println(oddAdd(100000)) } var count = 0 fun oddAdd(num: Int, total: Int = 0): Int { println("計算機第${++count}計算") return if (num == 1) { 1 + total } else { //這里尾遞歸，遞歸調用時整個函數中最后執行的語句的時候 oddAdd(num - 1, num + total) } } ~~~ 運行結果 ``` .................. 計算機第6393計算 計算機第6394計算 計算機第6395計算 Exception in thread "main" java.lang.StackOverflowError at sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:691) .................... ``` 針對以上代碼我們看到，到一定時候，就出現了內存溢出。能不能去解決這樣的問題呢？**如果遞歸是尾遞歸，是可以在編譯階段進行尾遞歸優化的**。python、scala都支持尾遞歸優化，**Kotlin同樣也是支持尾遞歸優化的，直接使用tailrec關鍵字即可，Kotlin中提供了一個tailrec修飾符來修飾尾遞歸函數，此時編譯器會優化該尾遞歸函數，將尾遞歸函數轉化為while循環，程序會快速高效地運行，并且無堆棧溢出的風險**。參考代碼： ~~~ fun main(args: Array<String>) { println(oddAdd(100000)) } var count = 0 //添加tailrec關鍵字，編譯器自動進行尾遞歸優化 tailrec fun oddAdd(num: Int, total: Int = 0): Int { println("計算機第${++count}計算") return if (num == 1) { 1 + total } else { //這里尾遞歸，遞歸調用時整個函數中最后執行的語句的時候 oddAdd(num - 1, num + total) } } ~~~ 運行結果 ``` ......... 計算機第99998計算 計算機第99999計算 計算機第100000計算 705082704 Process finished with exit code 0 ``` **如果，給一個非尾遞歸函數添加tailrec關鍵字，IDEA也是會自動提示的**，參考截圖：  其實我們還可以進一步了解編譯器，到底對尾遞歸函數進行了什么優化，我們查看編譯轉換的java文件（字節碼文件，Decompile），發現就是把遞歸轉換成了while循環，參考截圖：  ### 官方文檔闡述[尾遞歸函數](http://www.kotlincn.net/docs/reference/functions.html#尾遞歸函數) Kotlin 支持一種稱為[尾遞歸](https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8)的函數式編程風格。 這**允許一些通常用循環寫的算法改用遞歸函數來寫，而無堆棧溢出的風險。 當一個函數用`tailrec`修飾符標記并滿足所需的形式時，編譯器會優化該遞歸，留下一個快速而高效的基于循環的版本**： ``` val eps = 1E-10 // "good enough", could be 10^-15 tailrec fun findFixPoint(x: Double = 1.0): Double = if (Math.abs(x - Math.cos(x)) < eps) x else findFixPoint(Math.cos(x)) ``` 這段代碼計算余弦的不動點（fixpoint of cosine），這是一個數學常數。 它只是重復地從 1.0 開始調用 Math.cos，直到結果不再改變，對于這里指定的`eps`精度會產生 0.7390851332151611 的結果。最終代碼相當于這種更傳統風格的代碼： ``` val eps = 1E-10 // "good enough", could be 10^-15 private fun findFixPoint(): Double { var x = 1.0 while (true) { val y = Math.cos(x) if (Math.abs(x - y) < eps) return x x = Math.cos(x) } } ``` **要符合`tailrec`修飾符的條件的話，函數必須將其自身調用作為它執行的最后一個操作。在遞歸調用后有更多代碼時，不能使用尾遞歸，并且不能用在 try/catch/finally 塊中**。目前尾部遞歸只在 JVM 后端中支持。