5-2-函数递归

1. 什么是递归？

递归就是一个函数在函数体内调用它自己。它通常包含两个部分：

递归条件（递推部分） —— 函数调用自身以解决子问题。
终止条件（递归出口） —— 在某个条件满足时不再调用自身，防止无限循环。

代码示例

fun factorial(n: Int): Int {
    return if (n == 0 || n == 1) {
        1 // 递归出口
    } else {
        n * factorial(n - 1) // 递归调用
    }
}

fun main() {
    println(factorial(5)) // 输出 120
}

尾递归

Kotlin 还支持一种尾递归函数的编程方式，当函数最后一步调用自己，并直接返回这个调用的结果，可使用尾递归语法。

需要注意的是，尾递归不能在异常处理的try、 catch 、 finally 块中使用。

代码示例

fun fact(n: Int,): Int {
    return if(n == 1) 1
    else n + fact(n - 1)
}

上述代码只是普通的递归调用，最后的操作是 n + ...，也就是在递归调用 fact(n-1) 之后还要加 n，所以不是尾递归。

尾递归写法

tailrec fun fact(n: Int, acc: Int = 0): Int {
    return if (n == 0) acc
    else fact(n - 1, acc + n)

上述代码就是尾递归的形式，递归调用是函数最后一步，因此编译器可以优化成循环。