尾调用和尾递归

讲尾调用和尾递归优化之前，需要知道函数执行栈。

执行栈

执行栈，也叫调用栈，具有LIFO（Last in, First out 后进先出）结构，用于存储在代码执行期间创建的所有执行上下文。

当JavaScript引擎首次读取脚本时，会创建一个全局执行上下文并将其Push到当前执行栈中。每当发生函数调用时，引擎都会为该函数创建一个新的执行上下文并Push到当前执行栈的栈顶。

引擎会运行执行上下文在执行栈栈顶的函数，根据LIFO规则，当此函数运行完成后，其对应的执行上下文将会从执行栈中Pop出，上下文控制权将转到当前执行栈的下一个执行上下文。

实例

let a = 'Hello World!';
function first() {  
  console.log('Inside first function');  
  second();  
  console.log('Again inside first function');  
}
function second() {  
  console.log('Inside second function');  
}
first();  
console.log('Inside Global Execution Context');

什么是尾调用Tail Call？

尾调用是指执行某个函数时，最后异步是一个函数调用，并且被调用函数的返回值直接被当前函数返回。

function f() {
	return g();
}

尾调用优化

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

总所周知，函数调用会在内存形成一个"调用记录"，又称"调用帧"（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用记录上方，还会形成一个B的调用记录。等到B运行结束，将结果返回到A，B的调用记录才会消失。如果函数B内部还调用函数C，那就还有一个C的调用记录栈，以此类推。所有的调用记录，就形成一个"调用栈"（call stack）

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

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

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

// 等同于
g(3);

什么是尾递归？

递归函数调用自身。

尾递归，在尾部直接调用自身的递归函数

尾递归，比线性递归多一个参数，这个参数是上一次调用函数得到的结果； 所以，关键点在于，尾递归每次调用都在收集结果，避免了线性递归不收集结果只能依次展开消耗内存的坏处比线性递归多一个参数，这个参数是上一次调用函数得到的结果；

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生"栈溢出"错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。

尾递归优化

尾递归的特殊形式决定了这种递归代码在执行过程中是可以不需要回溯的(通常的递归都是需要回溯的). 如果编译器针对尾递归形式的递归代码作了这种优化, 就可能把原本需要线性复杂度栈内存空间的执行过程用常数复杂度的空间完成.

尾递归优化主要是针对栈内存空间的优化, 这个优化是O(n)到O(1)的; 至于时间的优化, 其实是由于对空间的优化导致内存分配的工作减少所产生的, 是一个常数优化, 不会带来质的变化.

示例1 累加器 1+....+100

//普通递归
function sum(n) {
	if(n <=1) {
    	return n;
    }
    return n + sum(n-1);
}
//尾递归

function sum(n) {
	function sumFun(a, n){
		if (n == 0) return a;
		return sumFun(a+n, n-1);
	}
    return sumFun(0, n);
}

拿sum(5)=5＋sum(4)举例

普通的递归，算到最后一步的时候，计算机内存里存储的值是5＋4＋3＋2＋sum(1)，这里是4个数字，和一个需要计算的函数sum()，然后再把这5个数字加起来，得出结果15。

尾递归，算到最后一步的时候，计算机内存里存储的值是14+sum(1)，这里是1个数字，和一个需要计算的函数sum()。

对于整形数字int类型来说，在计算机内存储每个2，3，4，5和存储14所占的内存空间是一样的，虽然表达的都是14这个信息，前者的内存占用是后者的4倍。所以可以看出普通递归和尾递归的区别。

示例2"计算斐波那契数列第n项"

实现1：最直观的递归实现(树形递归)

function fib1(n) {
	if(n===0||n===1){
    	return 1;
    }
    return fib1(n-1)+fib1(n-2);
}

实现2：线形递归

function fib2(n) {
	function fib_res(a ,b, n) {
    	if(n===0||n===1){
    		return 1;
    	}
        return a + fib_res(b, a+b, n-1);
    }
    return fib_res(1, 1, n);
}

实现3：迭代(循环)实现

function fib3(n) {
	let a = 1
    let b = 1;
    for(let i = 0; i < n; i++) {
    	let _a = a;
        let _b = a+b;
        a = _a;
        b = _b;
    }
}

实现4： 尾递归实现

function fib4(n) {
	function fib_res(a ,b, n) {
    	if(n===0||n===1){
    		return a;
    	}
        return fib_res(b, a+b, n-1);
    }
    return fib_res(1, 1, n);
}