Kotlin尾递归优化-原理篇

, , , ,

递归

在编程中我们把函数调用自身称之为递归调用

在JVM中每一次函数调用都会创建一个栈帧用于存储局部变量表、操作数栈、方法出口等信息。如果我们的递归层次过深，创建大量的栈帧，会消耗大量的时间和空间，若调用栈深度大于JVM所允许的最大深度，程序还会会抛出StackOverflowError。

尾递归

在递归函数中，递归调用发生在函数结尾，称之为尾递归

例如：

1
2
3
4
5
6
7
8
// Koltin Code
fun f0(x: Int): Int {
    var y = x + 1;
    if (y >= 10000) {
        return y;
    }
    return f0(y);
}

例中函数f0在尾部调用f0自身，这样的函数就是尾递归函数。

如果递归调用不是在函数的尾部，则不是尾递归，例如：

1
2
3
4
5
6
7
8
// Koltin Code
fun f1(x: Int): Int {
    var y = x + 1;
    if (y >= 10000) {
        return y;
    }
    return f1(y) + 1;
}

例中函数f1在尾部执行的是+1操作，这样的函数就不能称之为尾递归函数。

尾递归优化

我们可以通过javap命令来查看函数f0所生成的字节码，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// java byte code
 public static final int f0(int);
    descriptor: (I)I 
    flags: ACC_PUBLIC, ACC_STATIC, ACC_FINAL
    Code:
      stack=2, locals=2, args_size=1
         0: iload_0        
         1: iconst_1
         2: iadd
         3: istore_1
         4: iload_1
         5: sipush        10000
         8: if_icmplt     13
        11: iload_1
        12: ireturn
        13: iload_1
        14: invokestatic  #35                 // Method f0:(I)I
        17: ireturn

接下来我们对这段字节码做一下解读

  • descriptor: (I)I //表示该函数接受一个int类型返回一个int类型
  • flags: ACC_PUBLIC, ACC_STATIC, ACC_FINAL //表示该函数修饰符 public static final
  • stack=2, locals=2, args_size=1 //表示操作数栈的深度为2，局部变量表的空间为2（分别存放x,y）,接收一个参数（x）
  • iload_0 //将局部变量表中的第0个元素（变量x）压入操作数栈
  • iconst_1 //将Int类型1压入操作数栈
  • iadd //弹出操作数栈栈顶的两个int值进行相加操作，并将结果压入操作数栈
  • istore_1 //弹出操作数栈栈顶int值，并存入局部变量表中的第1个空间（y）
  • iload_1 //将局部变量表中的第1个元素（y），压入操作数栈
  • sipush 10000 //将int类型的值10000压入操作数栈
  • if_icmplt 13 //弹出操作数栈 栈顶的两个int类型值进行比较，若栈前小于后（既 y<1000）则跳转到13号指令，反之继续执行下面的指令
  • iload_1 //将局部变量表中的第1个元素（y），压入操作数栈
  • ireturn //将操作数栈 栈顶的int类型的值返回
  • iload_1 //将局部变量表中的第1个元素（y），压入操作数栈
  • invokestatic #35 // Method f0:(I)I //执行常量池中35号值所指向的方法（既函数f0本身），弹出操作数栈栈顶的int值作为参数传入，并将执行的结果压入操作数栈
  • ireturn //将操作数栈 栈顶的int类型的值返回

从上面的字节码我们可以看出通过invokestatic #35指令调用函数本身，在做递归调用。invokestatic #35指令执行完之后函数就return了，那么invokestatic #35做了什么呢？其实很简单，就是又建了一个和上面完全相同栈帧，执行和上面相同的指令，周而复始。程序退出递归的条件是y >= 10000，假如我调用f0的时候传入的参数是0，invokestatic #35带来的就是创建10 000个栈帧，如果我们把上面的判断条件改为y >= 1000000，StackOverflowError就来了。

我们能否对此做一下优化呢？

之前我们提到了尾递归的概念，函数f0的递归调用在return前的最后一步。也就是invokestatic #35指令。我们也提到了invokestatic #35就是创建了一个相同栈帧，执行相同的指令。那么我们能否不去创建一个新的栈帧，复用本栈帧呢？因为执行完invokestatic #35指令就是return了，栈帧中的局部变量表，操作数栈也用不到了。

于是我可以将上面的字节码优化为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// java byte code
 public static final int f0(int);
    descriptor: (I)I 
    flags: ACC_PUBLIC, ACC_STATIC, ACC_FINAL
    Code:
      stack=2, locals=2, args_size=1
         0: iload_0        
         1: iconst_1
         2: iadd
         3: istore_1
         4: iload_1
         5: sipush        10000
         8: if_icmplt     13
        11: iload_1
        12: ireturn
        13: iload_1
    **  14: istore_0
    **  15: goto          0

上面的字节码中我们去掉了 invokestatic 、ireturn指令，换成了istore_0和goto指令。因为invokestatic将栈顶的值传入新的栈帧之后也是存入局部变量表中的第0个空间，所以这里我们直接将栈顶的值弹出，存入本栈帧局部变量表中的第0个空间。然后我们用goto指令跳转到第0号指令，开始执行。程序的执行结果是完全一样的。没错，invokestatic被我们拿掉了，也就是说这是我们的程序不存在递归调用了，调用函数的开销不存在了，StackOverflowError也不会遇到了，f0函数的调用自始至终只会产生一个栈帧。

上面字节码用到了goto指令， “if_icmplt + goto”把我们的程序变成了循环，类似于大概如下的Java代码：

1
2
3
4
5
6
7
8
9
10
// java code
public static final int f0(int x) {
      while(true) {
         int y = x + 1;
         if (y >= 10000) {
            return y;
         }
         x = y;
      }
   }

tailrec关键字

Kotlin的编译器默认是不会对尾递归做优化的，如果我们想要编译器对尾递归做优化，就必须在函数声明时候加上tailrec关键字，如：

1
2
3
4
5
6
7
8
// Koltin Code
tailrec fun f0(x: Int): Int {
    var y = x + 1;
    if (y >= 10000) {
        return y;
    }
    return f0(y);
}

这样我们就可以用递归的思想编写代码，以循环的性能执行程序，同时也不用担心StackOverflowError了，但是有一个条件就是递归调用必须在函数的尾部，因为这样我们才可以复用栈帧。