前言

尾调用

一个函数内最后一个动作是调用函数的情形（即这个调用的返回值直接被当前函数返回的情形）

fun shape(x: Int): Int {
    return rect(x)
}

尾递归

尾调用在尾部位置调用函数本身的情形。尾递归属于递归的一种特殊情形。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。

fun shape(x: Int): Int {
    return shape(x-1)
}

尾递归在普通尾调用的基础上，多出了2个特征：

• 在尾部调用的是函数自身 （Self-called）；
• 可通过优化，使得计算仅占用常量栈空间 (Stack Space)。

在程序运行时，计算机会为应用程序分配一定的内存空间；应用程序则会自行分配所获得的内存空间，其中一部分被用于记录程序中正在调用的各个函数的运行情况，这就是函数的调用栈。常规的函数调用总是会在调用栈最上层添加一个新的栈帧（stack frame），这个过程被称作入栈或压栈（意即把新的帧压在栈顶）。当函数的调用层数非常多时，调用栈会消耗不少内存，甚至会撑爆内存空间（栈溢出），造成程序严重卡顿或意外崩溃。

尾调用优化 (TCO)

通过优化尾调用的调用栈，可以减少内存空间的使用，提高运行速度。其中，对尾递归情形的优化效果最为明显。尾递归优化可以使原本 O(n) 的调用栈空间变为 O(1)。

Kotlin

tailrec

tailrec，即 tail recursive 的缩写

Kotlin 通过 tailrec 修饰符来标记函数完成尾递归优化操作。所谓优化，即将递归操作改写成迭代操作，避免栈溢出。

以斐波那契数列为例：

• 简单递归暴力直接，但是存在很多重复计算；
• 尾递归避免重复计算，缩短计算时间，但是随着数列的增加（尝试 n = 15000），调用栈膨胀，最终会引发 StackOverflow；
• 采用 tailrec 尾递归优化，在尾递归的基础上有效避免栈溢出错误。

简单递归

/**
 * 递归实现
 */
fun fibonacci(n: Int): Int {
    if (n == 0 || n == 1) {
        return n
    }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

尾递归

/**
 * 尾递归
 */
fun fibonacci(n: Int, a: Long = 0, b: Long = 1): Long {
    return if (n == 0 || n == 1) {
        n.toLong()
    } else {
        fibonacci(n - 1, b, a + b)
    }
}

尾递归优化

/**
 * 尾递归优化
 */
tailrec fun fibonacciTco(n: Int, a: Long = 0, b: Long = 1): Long {
    return if (n == 0 || n == 1) {
        n.toLong()
    } else {
        fibonacciTco(n - 1, b, a + b)
    }
}

Decompile

When a function is marked with the tailrec modifier and meets the required formal conditions, the compiler optimizes out the recursion, leaving behind a fast and efficient loop based version instead。

根据 Kotlin 官方说明，tailrec 会告诉编译器，将尾递归代码改写成简单循环，以此达到优化的目的。查阅反编译 Java 代码可见一斑。

Tools -> Kotlin -> Show Kotlin Bytecode -> Decompile

public static final long fibonacciTco(int n, long a, long b) {
   while(n != 0 && n != 1) {
      int var10000 = n - 1;
      long var10001 = b;
      b += a;
      a = var10001;
      n = var10000;
   }

   return (long)n;
}

总结

tailrec 可能平时写代码时并不常用，但是我们需要了解它能为我们提供何种便利，并且掌握一些计算机科学的概念。关于 tailrec ，网上也有一些吐槽，有些开发者认为，为什么 Kotlin 不能识别尾递归而自动优化呢？大家的初衷都是好的，但是不同的语言有不同的优秀特性，个人认为通过修饰符限定的方式，为开发者提供开关是相对合适的选择。