Kotlin尾递归优化

Kotlin尾递归优化

尾调用（Tail Call）是函数式编程的一个重要概念，本文介绍它的含义和用法。

1. 尾递归

​ 如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。

​ 简单地说，尾递归就是某个函数的最后一步是调用另一个函数，且在这一步中，除了调用函数外，前后没有其他操作。

​ 因此，尾递归就是递归的一种特殊形式。

//尾调用
fun tailCall(n : Int): Int{
    return f(n)
}

//不是尾调用
fun notTailCall(n : Int): Int{
    return n + f(n)
}

//不是尾调用
fun notTailCallEither(n : Int):Int{
    return f(n) + n
}
//这两种函数调用不是尾调用， 是因为它们在最后一步除了调用函数之外还有其它操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

​ 要注意的是，尾调用不一定出现在函数尾部，只要是最后一步操作即可

//尾调用
fun cumsum(n:Int, res:Long):Long = if (n == 1) n+res else cumsum(n - 1, n+res)
//尾调用
fun cumsum(n:Int, res:Long):Long {
    if (n == 1) 
        return n+res 
    else 
        return cumsum(n - 1, n+res)
}
//这些函数结束前的最后一步都只有函数调用，因此是尾调用
1
2
3
4
5
6
7
8
9
10

2. 尾调用优化

​ 尾调用之所以与其他调用不同，就在于它的特殊的调用位置。

​ 我们知道，函数调用会在内存形成一个"调用记录"，又称"调用帧"（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用记录上方，还会形成一个B的调用记录。等到B运行结束，将结果返回到A，B的调用记录才会消失。如果函数B内部还调用函数C，那就还有一个C的调用记录栈，以此类推。所有的调用记录，就形成一个"调用栈"（call stack）。

​ 由于尾调用是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。

fun f() {
  val m = 1;
  val n = 2;
  return g(m + n);
}
f();
 
// 等同于
fun f() {
  return g(3);
}
f();
 
// 等同于
g(3);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

​ 上面代码中，如果函数g不是尾调用，函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后，函数f就结束了，所以执行到最后一步，完全可以删除 f() 的调用记录，只保留 g(3) 的调用记录。

​ 这就叫做"尾调用优化"（Tail call optimization），即只保留内层函数的调用记录。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存。这就是"尾调用优化"的意义。

3. 递归函数的改写

有示例累加函数，计算从1到n之和

fun cumsum(n:Int):Long = if (n == 1) 1 else n+cumsum(n-1)

val res = cumsum(n)
1
2
3

当输入的n数值过大时，会造成栈溢出异常StackOverflowError：

因此，我们需要对这样的递归函数改写为尾递归函数，确保最后一步只调用自身

因此我们可以得到以下代码：

fun cumsum(n:Int, res:Long):Long = if (n == 1) n+res else cumsum(n - 1, n+res)

var res = 0
res = cumsum(n, res)
1
2
3
4

这样，我们完成了从普通递归函数到尾递归函数的改写，但这样的改写降低了可读性，其他人在函数使用时会造成困惑：为什么计算n的累加和需要传入n和0呢？

要解决代码的使用问题，我们可以采取两种办法：

3.1 函数封装

在尾递归函数外提供一个正常形式的函数：

//尾递归函数计算累加和
fun cumsum(n:Int, res:Long):Long = if (n == 1) n+res else cumsum(n - 1, n+res)

//正常形式函数调用尾递归函数
fun getCumsum(n:Int) = cumsum(n, 0)

val res = getCumsum(n)
1
2
3
4
5
6
7

3.1.1 柯里化

​ 柯里化（Currying），就是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数，并且返回接受余下的参数且返回结果的新函数

fun cumsum(n:Int, res:Long):Long = if (n == 1) n+res else cumsum(n - 1, n+res)
fun currying(func:(Int, Long)->Long, res:Long) = fun(n:Int) = func(n, res)

val curriedCumsum = currying(::cumsum, 0)
val res = curriedCumsum(n)
1
2
3
4
5

3.2 参数默认值

通过使用参数默认值，我们可以很轻松地将传入两个参数转为传入一个参数

fun cumsum(n:Int, res:Long = 0):Long = if (n == 1) n+res else cumsum(n - 1, n+res)

val res = cumsum(n)
1
2
3

4. Kotlin尾递归函数优化

在Kotlin中，对尾递归函数特别进行了优化，要使用优化，除了要将递归函数形式改写为尾递归函数外，还要在函数前加上关键字tailrec

tailrec fun cumsum(n:Int, res:Long = 0):Long = if (n == 1) n+res else cumsum(n - 1, n+res)
1

如果没有添加关键字tailrec，即使将递归函数形式改写为尾递归函数，Kotlin也不会对函数进行尾递归优化