Kotlin 函数嵌套

本文参考自：

• 朱涛 · Kotlin 编程第一课 (geekbang.org)
• 递归与尾递归总结 - Rabbit_Dale - 博客园 (cnblogs.com)
• kotlin学习笔记之尾递归优化（tailrec）_mictoy_朱的博客-CSDN博客_kotlin tailrec

---

使用方法

在 Kotlin 中，我们可以在函数的代码块中创建另一个新的函数并使用该函数。并且该函数可以使用外部函数的变量。

如下方的代码；

fun outerMethod() {
    var sum = 0
    
    // 计算 1 + 2 + 3 + ...
    fun innerMethod(c: Int = 10) {
        sum += c
        if (c > 0)
        	innerMethod(c - 1)
    }  
    
    innerMethod()
  	println(sum)
}

fun main() {
    outerMethod()
}

---

使用场景

函数嵌套在工程中应尽量少的使用，容易造成代码可读性的降低。

但是在两种情况下可以创建内部函数：

1. 在某些情况下需要临时使用 递归 函数，如上文中的代码。
2. 不希望被外部函数访问到的函数。

---

尾递归

实际上，在函数式编程当中，我们有时候也会使用递归来替代循环。

我们知道，递归都是有调用栈开销的，所以我们应该尽量使用 尾递归。对于这种类型的递归，在经过栈复用优化以后，它的开销就可以忽略不计了，我们可以认为它的空间复杂度是 O(1)。

尾递归就是从最后开始计算，每递归一次就算出相应的结果，也就是说, 函数调用出现在调用者函数的尾部，因为是尾部，所以根本没有必要去保存任何局部变量，直接让被调用的函数返回时越过调用者，返回到调用者的调用者去。

尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径。

尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。

尾递归的特点

• 递归的一种特殊形式
• 调用自身后无其他操作
• tailrec 关键字提示编译器尾递归优化

示例代码：

data class ListNode(val value: Int, var next: ListNode? = null)

fun findListNode(head: ListNode?, value: Int): ListNode? { // 定义一个递归函数
    head ?: return null
    if (head.value == value) return head
    return findListNode(head.next, value) // return 除了调用自己，没有多余的操作，所以是尾递归
}

尾递归优化的使用

在 Kotlin 语言中，我们即使写出了符合尾递归的递归函数，编译器也不会自动帮我们进行优化。

我们需要在 fun 关键字前面加上 tailrec 关键字以表示我们需要进行尾递归优化。

示例代码1：

data class ListNode(val value: Int, var next: ListNode? = null)

tailrec fun findListNode(head: ListNode?, value: Int): ListNode? { // 定义一个递归函数
    head ?: return null
    if (head.value == value) return head
    return findListNode(head.next, value) // return 除了调用自己，没有多余的操作，所以是尾递归
}

示例代码2：

fun recursionLoop(): Int {
// 变化在这里
//     ↓
    tailrec fun go(i: Int, sum: Int): Int =
        if (i > 10) sum else go(i + 1, sum + i)

    return go(1, 0)
}

尾递归优化的实质

通过对上文中的 findListNode 方法对 加了 tailrec 关键字 与 去除 tailrec 关键字 的两份代码分别进行反编译，我们发现：

• 没有优化的 findListNode 对应的 Java 代码依然是递归函数，并且递归运行次数较大时出现了 StackOverflowError 错误；

  

• 优化后（即添加了 tailrec 关键字）的 findListNode 方法对应的 Java 代码已经不再是递归函数，而是通过循环来实现功能，这样就不会再出现 stackoverflowerror 了。

  

这样我们就在 Kotlin 中既实现了递归函数代码简洁的优势，又规避了在 Java 中使用递归函数容易出出现的问题。