尾递归并不是函数式编程才有的特性，c++ 里面也是有的。第一次接触尾递归，是在 UW的coursera课程中，第二次是在sensetime的面试中，面试官问我了解尾递归吗，什么情况下编译器可以用尾递归优化。这里虽然使用 scala作为实例讲解尾递归，但请注意，这并不是scala语言中才有的特性

先说定义，尾递归就是一种特殊的递归，这种递归编译器可以优化，怎么优化呢？如果递归的过程中可以用被调用函数的栈将调用者函数的栈完全覆盖掉(而和不覆盖掉的运行效果是一样的)，那么编译器就可以用尾递归优化，

tail recusion 尾递归

这是课程中的一个定义

example1

def gcd(a:Int,b:Int):Int={
    if(b==0)a
    else gcd(b,a%b)
}

这里函数 gcd 有一个递归调用，可是其实可以完全用递归函数的栈覆盖掉原来的函数，而不产生任何问题
tail recusion 尾递归

它的函数调用栈大概长成这样，左非尾递归，右尾递归

可以见到，右边用来尾递归优化的栈并不会向下继续增长，而是将原来的栈给覆盖掉

example 2

def fact(n :Int):Int={
    def factAcc(ret:Int,n :Int):Int={
        if(n==0)ret
        else factAcc(ret*n,n-1)
    }
    factAcc(1,n)
}

这是计算 n! 的尾递归版本，可以看到，factAcc的if-else的两个分支都是直接即时计算的(不需要保存任何中间结果)，也就是说计算，和调用顺序是线性的

来看一下普通的版本

def factNotTailRec(n:Int):Int={
    if(n==0)1
    else n*factNotTailRec(n-1)
}

注意 else分支,这里有两个计算，除了计算 fact(n-1) 的结果之外，还需要将这个结果乘上n，这使得计算是二叉的，也就是不能直接用 fact(n-1)的结果直接作为fact(n) 的结果，这带来了栈的开销，使得栈中必须要存储 n。

验证尾递归优化

我们如何验证编译器确实做了尾递归优化呢？

直接看编译后的字节码

这肯定是最直接的方式，但也很难，估计能学到这儿的人并不多

tialrec 声明

import scala.annotation.tailrec

def gcd(a:Int,b:Int):Int={
    if(b==0)a
    else gcd(b,a%b)
}

def fact(n :Int):Int={
    @tailrec
    def factAcc(ret:Int,n :Int):Int={
        if(n==0)ret
        else factAcc(ret*n,n-1)
    }
    factAcc(1,n)
}

这样如果 factAcc

不是tail recursion 那么编译器会报错

打印递归调用栈

def fact(n :Int):Int={

    def factAcc(ret:Int,n :Int):Int={
        if(n==0){
            val stackArray = Thread.currentThread().getStackTrace()
            stackArray.foreach(println)
            ret
        }
        else factAcc(ret*n,n-1)
    }
    factAcc(1,n)
}


fact(5)

在递归结束的时候加了一个打印递归调用栈的操作，这里如果编译器使用了尾递归，我们能看到的是 fact->factAcc 1

不会有中间调用结果


java.lang.Thread.getStackTrace(Thread.java:1559)
$line5.$read$$iw$$iw$.factAcc$1(<console>:16)
$line5.$read$$iw$$iw$.fact(<console>:22)

上面是我本地的输出结果

可以见到fact 调用之后，直接就是 factAcc$1,没有其他调用了

reference