/ 算法  

递归与尾递归

递归的问题

函数的递归调用是通过栈来实现的，每一次函数调用都会把当前函数的状态，如变量，返回地址保存在栈中一直到函数返回才能出栈。因为程序运行时，栈的大小一般很有限（在 chrome 中运行下面的代码可以计算出 chrome 给每个线程的栈大小），因此如果递归调用的层次如果过多，将会使栈区溢出。

尾递归

尾递归就是函数最后的语句是调用函数自身，但调用自己的时候，已经不再需要上一个函数的环境了。

1
2
3
4
5
6
function factorial(n,a){
	if(n<=0)
		return 0;
	if(n == 1)
		return a;
	return factorial(n-1,a*n);

相比较之前一般形式的递归代码，有两个不同的地方：

  • 递归调用时，把 n 当做参数传给了递归函数，无需等待递归调用返回后参与计算。
  • 最终的计算结果在最后一次递归调用后产生，无需回溯。

我们通过这种形式，解决了需要函数回跳才能计算的问题，但最后产生的计算结果仍然需要层层的回调，但这种代码的形式对于普通的递归来说，编译器更容易对其进行优化。这种特殊的递归叫做尾递归，从递归代码形式上看，它自身的调用是函数的最后一个操作。尾递归的目的是为了优化，而优化的目标是减少栈的空间。

尾递归是递归的一种优化

按照尾递归的定义，尾递归就至少必须解决一般递归的两个问题：

  • 不能重复计算
  • 重复利用栈空间

然而尾递归是为编译器优化的目的，所以还要依赖于编译器的实现，如果一种语言不支持尾递归，那么尾递归也就仅仅是个形式上递归了，JavaScript 就是这样的语言，因为它无法优化栈空间的利用。

实际上尾递归一直被看作一种编译技巧，特别是对于函数式编程语言来说，尾递归的编译器实现做当做的一种必须的标准

es6 中的尾调用优化

尾调用被识别出来，重复利用了已存在的栈结构来进行递归，移除了之前函数调用的本地变量和状态。

如果使用了BABEL，它会直接、自递归地处理尾调用。

爆栈问题解决

递归改循环