[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 后端中支持。