尾递归优化，以及在C、Java与Kotlin语言中的对比

Tail-Recursion（尾递归）

  • 尾递归

尾递归定义为递归函数，其中递归调用是函数执行的最后一条语句，所以在递归调用之后基本上没有什么可执行的了。一般尾递归函数比线性递归函数多一个参数(这个参数是上一次调用函数得到的结果)。关键点在于，尾递归每次调用都在收集结果，避免了线性递归不收集结果只能依次展开消耗内存的坏处。

  • 尾递归优化

尾递归调用优化（Tail-Call Optimization）指在一定条件下，编译器可以直接利用跳转指令取代函数调用指令，来"模拟"函数的调用过程。所以尾递归优化主要是对栈内存空间的优化，从O(n)到O(1)。对于时间的优化是由于对空间的优化导致内存分配的工作减少所产生的，是一个常数级别的优化。

目的是

  1. 省去函数调用栈帧的不断创建和销毁过程，
  2. 使递归函数在整个调用期间都仅在栈内存中维护着一个栈帧。
  • 函数式编程中的递归与迭代

在一些函数式编程语言(如Scala)中是鼓励使用递归，而不是循环来解决问题。这是因为循环会引入中间变量,而函数范式强调的是无副作用，强调函数计算的纯粹性，每个函数的执行都是没有副作用的，函数所有功能就是返回一个新的值，没有其他行为，尤其是不得修改外部变量的值。

Recursion（递归） VS Tail-Recursion（尾递归）

  • 递归阶乘
public static int factorialRecursion(final int number) {
    if (number == 1) return number;
        else return number * factorialRecursion(number - 1);
}

// 当调用factorialRecursion(5)时 栈的情况:

// factorialRecursion(5)
// 5 * factorialRecursion(4)
// 5 * (4 * factorialRecursion(3))
// 5 * (4 * (3 * factorialRecursion(2)))
// 5 * (4 * (3 * (2 * factorialRecursion(1))))
// 5 * (4 * (3 * (2 * 1)))
// 5 * (4 * (3 * 2))
// 5 * (4 * 6)
// 5 * 24
// 120

这里就是典型的线性递归创建栈内存累积而后计算收缩，从左到右，达到顶峰，再从右到左收缩。栈扩展的原因是在没有递归到底之前，程序的中间变量会一直保存着，因此每一次递归都需要开辟一个新的栈空间来保存中间变量。

  • 尾递归阶乘
 public static int factorialTailRecursion(final int factorial, final int number) {
        if (number == 1) return factorial;
        else return factorialTailRecursion(factorial * number, number - 1);
}

// 当调用factorialTailRecursion(1,5)时 栈的情况:

// factorialTailRecursion(1, 5)
// factorialTailRecursion(5, 4)
// factorialTailRecursion(20, 3)
// factorialTailRecursion(60, 2)
// factorialTailRecursion(120, 1)
// 120

分析上面递归函数栈累积的原因就是在每次return的时候都会附带一个变量，因此只需要在return的时候不附带这个变量即可。尾递归使用一个参数来保存上一轮递归的结果，把变化的参数传递给递归函数的变量了。

尾递归优化后，通过每轮递归结束后刷新当前的栈空间，复用了栈，克服了线性递归栈内存累积而后计算收缩，存在栈溢出风险。

对比下来可以看到，线性递归创建栈内存累积而后计算收缩，尾递归只会占用恒量的内存(类似迭代)。

尾递归优化 - C

尾递归优化依赖于编译器实现。C语言以GCC为例，在编译时指定了最高的编译优化等级 “-O3”，对比汇编代码，编译器并没有进行任何 call 指令的调用过程，而是使用跳转指令（如je、jne、jle等）来替换函数调用时所使用的 call 指令，相当于使用while循环条件代替了递归函数调用。

// 源代码
int factorial_tail(int n, int a) {
    if (n == 0) return a;
    return factorial_tail(n - 1, n * a);
}

// GCC 默认编译优化等级 编译后汇编代码
factorial_tail:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], edi
        mov     DWORD PTR [rbp-8], esi
        cmp     DWORD PTR [rbp-4], 0
        jne     .L2
        mov     eax, DWORD PTR [rbp-8]
        jmp     .L3
.L2:
        mov     eax, DWORD PTR [rbp-4]
        imul    eax, DWORD PTR [rbp-8]
        mov     edx, DWORD PTR [rbp-4]
        sub     edx, 1
        mov     esi, eax
        mov     edi, edx
        call    factorial_tail
.L3:
        leave
        ret

// GCC 编译优化等级 -O3 编译后汇编代码
factorial_tail:
        mov     eax, esi
        test    edi, edi
        je      .L5
.L2:
        imul    eax, edi
        sub     edi, 1
        jne     .L2
.L5:
        ret

尾递归优化 - Java

Javac对Tail-Recursion并没有做特定的优化，参考stackoverflow link，可以得知原因:

因为在JDK许多类中，有许多安全敏感方法依赖于计算JDK库代码和调用代码之间的堆栈帧来确定谁在调用它们。Tail-recursion优化会改变堆栈上帧数，会破坏它并导致计算错误。因此JDK开发人员已经取代了这种机制。

  • Java模拟栈调用实现尾递归优化

设计一个函数接口代替递归中的栈帧，利用Stream将递归转换为迭代，

/**
 * @Author : lhr
 * @Date : 11:15 2019/8/3
 *
 * 尾递归函数式接口
 */
@FunctionalInterface
public interface TailRecursion<T> {

    /**
     * 用于递归栈帧之间的连接,惰性求值
     * @return 下一个递归栈帧
     */
    TailRecursion<T> apply();

    /**
     * 判断当前递归是否结束
     * @return 默认为false,因为正常的递归过程中都还未结束
     */
    default boolean isFinished(){
        return false;
    }

    /**
     * 获得递归结果,只有在递归结束才能调用,这里默认给出异常,通过工具类的重写来获得值
     * @return 递归最终结果
     */
    default T getResult()  {
        throw new Error("递归还没有结束,调用获得结果异常!");
    }

    /**
     * 及早求值,执行者一系列的递归,因为栈帧只有一个,所以使用findFirst获得最终的栈帧,接着调用getResult方法获得最终递归值
     * @return 及早求值,获得最终递归结果
     */
    default T invoke() {
        return Stream.iterate(this, TailRecursion::apply)
                .filter(TailRecursion::isFinished)
                .findFirst()
                .get()
                .getResult();
    }
}

设计一个对外统一的尾递归包装类，目的是达到可以复用的效果，包装递归方法 1[怎样调用下次递归]，2[递归的终止条件]

/**
 * @Author : lhr
 * @Date : 11:59 2019/8/3
 *
 * 使用尾递归的类,目的是对外统一方法
 *
 * 调用下次递归/结束本轮递归
 *
 */
public class TailInvoke {

    /**
     * 统一结构的方法，获取当前递归的下一个递归
     * @param nextFrame
     * @param <T>
     * @return
     */
    public static <T> TailRecursion<T> call(final TailRecursion<T> nextFrame) {
        return nextFrame;
    }

    /**
     * 结束当前递归，重写对应的默认方法的值,完成状态改为true,设置最终返回结果,设置非法递归调用
     *
     * @param value 最终递归值
     * @param <T>   T
     * @return 一个isFinished状态true的尾递归, 外部通过调用接口的invoke方法及早求值, 启动递归求值。
     */
    public static <T> TailRecursion<T> done(T value) {
        return new TailRecursion<T>() {
            @Override
            public TailRecursion<T> apply() {
                throw new Error("递归已经结束,非法调用apply方法");
            }

            @Override
            public boolean isFinished() {
                return true;
            }

            @Override
            public T getResult() {
                return value;
            }
        };
    }

}

Java尾递归优化，阶乘计算示例

   /**
     * 阶乘计算 -- 使用尾递归接口完成
     *
     * @param factorial 当前递归栈的结果值
     * @param number    下一个递归需要计算的值
     * @return 尾递归接口, 调用invoke启动及早求值获得结果
     */
    public static TailRecursion<Long> factorialTailRecursion(final long factorial, final int number) {
        if (number == 1)
            return TailInvoke.done(factorial);
        else
            return TailInvoke.call(() -> factorialTailRecursion(factorial + number, number - 1));
    }

    public static void main(String[] args) {
        //调用Invoke启动迭代并获取结果
        factorialTailRecursion(1, 10000000).invoke();
    }

尾递归优化-Kotlin

  • tailrec关键字

Kotlin 支持尾递归优化，这允许一些通常用循环写的算法改用递归函数来写，而无堆栈溢出的风险。 当一个函数用 tailrec 修饰符标记并满足所需的形式时，编译器会优化该递归，留下一个快速而高效的基于循环的版本。

tailrec fun factorialTailRecursion(factorial: Int, number: Int): Int {
    return if (number == 1) factorial
    else factorialTailRecursion(factorial * number, number - 1)
}

经过Kotlin编译器优化后的代码如下

public static final int factorialTailRecursion(int factorial, int number) {
      while(number != 1) {
         int var10000 = factorial * number;
         --number;
         factorial = var10000;
      }

      return factorial;
}

参考