Kotlin递归
介绍
我们主要使用函数让它们为我们执行某些操作：有时打印一个特定的数字，有时进行计算并返回结果。有时我们会把一个函数的返回值传给另一个函数，有时函数会调用其他函数来完成任务。
然而，函数还有一个更重要的用法。
递归
除了上述用法外，我们还可以让函数调用它自己，这种做法有时能让问题的解决变得更简单。当函数调用自己时，这个过程称为递归。
下面是一段演示函数打印星号 n 次的代码示例：
fun printStars(n: Int) {if (n < 1) returnprint("*")printStars(n - 1)
}
代码说明
这个函数的工作流程可以描述为：“如果还有星号没打印（n > 0），打印一个星号，然后用剩余星号数量（n-1）调用自己。”
我们来看一个更复杂的阶乘函数的例子。你已经知道阶乘是什么——这个数学概念可以算是递归的经典应用。
计算阶乘 f(n)，就是把所有小于等于 n 的正整数相乘，即 1 * 2 * 3 * 4 * … * n。可以理解为先用 4 乘以 3，结果 12，再乘以 2，依此类推。所以给定正整数 n，我们需要计算 n 乘以 (n-1) 的阶乘。如果知道了 f(n-1)，就能很容易算出 f(n)。基于这个思路，我们来写一个递归阶乘函数：
fun factorialRecursive(n: Int): Int {if (n == 0 || n == 1) return 1return n * factorialRecursive(n - 1)
}
代码说明
- 定义了一个函数名为
factorialRecursive，它接受一个整数n作为参数，并返回一个整数类型的结果（即Int） - 该函数用于计算
n!（n 的阶乘）
终止条件
来看下面这个例子：
fun printStars(n: Int) {print("*")printStars(n - 1)
}
乍一看，它和前面那个打印星号的函数很像，但有一个重大区别——它永远不会停止。它不停地调用自己，直到执行代码的机器内存耗尽（或发生其他严重错误）。
递归必须非常小心地使用。如果没有终止递归调用的条件，函数会陷入无限调用自身的循环，最终导致程序崩溃。因此，为了正确使用递归，避免让电脑耗尽内存，我们需要限制递归的深度，确保有一个终止条件。阶乘函数中的终止条件就是当 n 等于或小于 0 时停止。
递归跟踪
递归是一个比较难理解的主题，所以我们需要一些方法帮助跟踪递归函数的运行过程并看清最终结果。
你当然可以把代码复制粘贴到 IDE 运行，但如果出现栈溢出错误或者结果不符合预期，你可能不知道哪里出了问题。
这时我们可以通过“手动跟踪”来理解递归，逐步看看递归函数每一步都做了什么。
看下面这段代码：
fun m(x: Int, y: Int): Int {return if (x < y) {x} else {m(x - y, y)}
}
假如让你算 m(50, 7) 的返回结果，你可能会脑中默算几步，但到第 4、5 次调用就容易迷糊了。我们用如下方式手动跟踪：
m(50, 7) -> m(43, 7)m(43, 7) -> m(36, 7)m(36, 7) -> m(29, 7)m(29, 7) -> m(22, 7)m(22, 7) -> m(15, 7)m(15, 7) -> m(8, 7)m(8, 7) -> m(1, 7)m(1, 7) -> 1 // 到达基准条件，开始返回m(8, 7) -> 1m(15, 7) -> 1m(22, 7) -> 1m(29, 7) -> 1m(36, 7) -> 1m(43, 7) -> 1
m(50, 7) -> 1 // 答案是1
通过这种方式，我们可以轻松看懂函数的执行过程。如果换成 m(37, 10)，你会发现这个递归函数计算的是 x % y （取模运算）。
这个小技巧可以帮助你理解更复杂的递归，也能更直观地看到递归函数的运作。
用循环替代递归
每个递归函数都可以用相应的循环来实现。比如阶乘函数，每次调用 f(n) 都紧接着调用 f(n-1)，n 每次减 1。既然调用参数依次递减，我们为什么不直接用循环呢？
下面是一个非递归版本的实现：
fun factorial(n: Int): Int {var f = 1for (i in 1..n)f *= ireturn f
}
代码说明
- 定义一个函数
factorial，它接收一个整数n作为参数，返回值类型为Int。 - 这个函数的目的是计算
n!，也就是1 × 2 × 3 × ... × n。
递归的类型
递归有几种类型：
- 直接递归
函数直接调用自己一次，比如递归阶乘：
fun factorialRecursive(n: Int): Int = if (n == 0 || n == 1) 1 else n * factorialRecursive(n - 1)
- 间接递归
函数 A 调用函数 B，函数 B 又调用函数 A。比如下面的阶乘示例：
fun weirdFactorialRecursive(n: Int): Int = if (n == 0 || n == 1) 1 else factorialCompute(n)fun factorialCompute(n: Int): Int = n * weirdFactorialRecursive(n - 1)
- 尾递归
函数调用自身是函数执行的最后一步。
例如：
fun tailFactorialRecursive(n: Int, cur: Int = 1): Int {if (n == 0) return curreturn tailFactorialRecursive(n - 1, cur * n)
}
代码说明
尾递归重要的原因是现代编译器可以更高效地处理它。通常递归会在调用栈上保存当前函数的局部变量和状态，消耗时间和空间；而尾递归可以被优化成跳转，复用当前栈帧，节省资源。
- 多重递归
函数调用自身多次。经典例子是斐波那契数列：
fun fibonacci(n: Int): Int {if (n <= 0) return 0if (n == 1) return 1return fibonacci(n - 1) + fibonacci(n - 2)
}
但是这个实现效率极低，因为递归分支数量指数级增长。
优化
正如前面提到的，斐波那契多重递归很低效，因为很多值被重复计算。除了用循环替代递归，还有一种优化叫记忆化。
比如计算 f(6) 会计算 f(5) 和 f(4)，f(5) 又会计算 f(4)，导致 f(4) 被计算了两次。这个问题对更大数值更加严重。
如何避免重复计算呢？用一个数组保存已经计算过的结果，如果遇到已计算的值，直接使用，避免重复计算。示例：
val fibList = MutableList(1000){0}fun coolerFibonacci(n: Int): Int {if (n <= 0) return 0if (n == 1) return 1return if (fibList[n] != 0) fibList[n]else {fibList[n] = coolerFibonacci(n - 1) + coolerFibonacci(n - 2)fibList[n]}
}
另一种优化是用循环代替递归计算：
fun fibonacciLoop(n: Int): Int {var n0 = 0var n1 = 1for (i in 1 until n) {val cur = n0 + n1n0 = n1n1 = cur}return n1
}
记忆化适合多次重复计算的情况，而循环适合只计算一次的情况。不是所有递归都需要优化，关键是避免重复计算。
结论
尽管递归需要谨慎使用，但在某些类型的问题上，递归是非常方便的工具。解决递归问题时，我们只需要定义好基准条件（比如阶乘中 n 为 0 或 1 时返回 1）和递归条件（比如阶乘 n 的值依赖于阶乘 n-1），递归机制会帮我们完成剩下的工作。
递归最重要的意义在于实现复杂逻辑的简洁表达，尤其适合将一个问题拆解成若干更小子问题的情况。