TCO和TRO

¶尾调用优化TCO，尾递归优化TRO💯

¶递归方法会导致栈溢出

一个函数直接或间接地调用自身，是为直接或间接递归。如计算斐波那契数列：

public static int Fibonacci(int n)
{
    if (n < 2) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

在调用时，Fibonacci方法会不断调用自身。如果方法的初始调用参数很大，那么这个方法就可能会遇到栈溢出（StackOverflowException）。这个方法在执行的过程中每多增加一层递归需要存储临时参数的栈空间就是上一层的两倍，而在最终递归结束前，每一层的方法参数n的值都不会被释放（出栈），所以栈的深度将会以O(2^n）的空间复杂度越压越深，最终达到最大深度导致栈溢出。

¶尾调用

参考：👉尾调用优化

¶尾调用

尾调用是指某个函数的最后一步是调用另一个函数。

function f(x){
  return g(x);
}

上面代码中，函数f的最后一步是调用函数g，这就叫尾调用。

以下两种情况，都不属于尾调用。

// 情况一
function f(x){
  let y = g(x);
  return y;
}

// 情况二
function f(x){
  return g(x) + 1;
}

上面代码中，情况一是调用函数g之后，还有别的操作，所以不属于尾调用，即使语义完全一样。情况二也属于调用后还有操作，即使写在一行内。

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

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

¶尾调用优化⭐️

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

function f() {
let m = 1;
let n = 2;
return g(m + n);
}
f();

// 等同于
function f() {
return g(3);
}
f();

// 等同于
g(3);

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

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

¶尾递归☀️

改造之前的斐波那契函数成尾递归形式，需要提供两个累加器：

public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
    if (n == 0) return acc1;
    return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}

FibonacciTailRecursively方法多了两个acc参数，它的功能是在递归调用时“积累”之前调用的结果，并将其传入下一次递归调用中。区别于之前的方法：Fibonacci方法在递归调用后还需要进行一次加法，而FibonacciTailRecursively的递归调用属于方法的最后一个操作。这就是所谓的尾递归。

与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出。
尾递归的本质，其实是将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中。
尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。

¶总结📌

递归本质上是一种循环操作。纯粹的函数式编程语言没有循环操作命令，所有的循环都用递归实现，所以尾调用优化在函数式编程语言中常见。JavaScript则原本不支持尾调用优化，到其第6代语言核心标准“ECMAScript 6”开始规定程序引擎应在严格模式下使用尾调用优化。而且ECMAScript 6限定了尾位置不含闭包的尾调用才能进行优化。

对于上述求斐波那契数列的方法，在java中建议改为循环的方法实现。