面试题：Kotlin中尾递归的基本概念及应用场景

Question

请阐述Kotlin中尾递归的定义，并举例说明在哪些实际场景下使用尾递归可以优化内存。同时，写出一个简单的Kotlin尾递归函数示例。

Answer 1

尾递归定义

尾递归是一种特殊的递归形式，在递归调用返回时，它没有任何额外的操作（除了返回递归调用的结果），这使得编译器或运行时环境可以优化这种递归，将其转化为迭代形式，从而避免栈溢出问题，因为它不需要在栈中保存额外的上下文信息。

实际场景

1. 计算阶乘：传统递归计算阶乘随着数字增大容易栈溢出，尾递归可优化。例如计算大数的阶乘，普通递归可能在计算10000的阶乘时栈溢出，尾递归则可以顺利完成。
2. 遍历树形结构：当树形结构深度较大时，尾递归可避免栈溢出。比如文件系统目录树的深度遍历，普通递归在深度很深的目录结构下会栈溢出，尾递归可以优化。

尾递归函数示例

tailrec fun factorial(n: Int, acc: Int = 1): Int {
    return if (n <= 1) acc
    else factorial(n - 1, n * acc)
}

这里factorial函数是尾递归的，acc是累加器，每次递归调用时将当前的n与acc相乘，并将n减1传递给下一次递归调用，直到n小于等于1时返回acc。这样在计算阶乘时不会出现栈溢出问题。