1、普通递归
2、尾递归（Tail Recursion）
2.1、任何的递归，都可以转换成尾调用，然后优化
- 如果算法本身就是尾递归的，那么，可以直接改写成迭代，这是尾调用优化的一种特例。
- 如果算法本身是非尾递归的，那么，CPS 变换可以将算法改写成尾调用形式，从而可以进行尾调用优化。改写过后的空间复杂度仍然是 O (n)，只不过是从 O (n) 的栈变成了 O (n) 的 continuation chain，这个改变对支持尾调用优化的简单解释器是有意义的。
2.2、尾递归
简单来讲，尾递归是指在一个方法内部，递归调用后直接return，没有任何多余的指令了。
尾递归和一般的递归不同在对内存的占用，普通递归创建stack累积而后计算收缩，尾递归只会占用恒量的内存（和迭代一样）。
尾递归是把变化的参数传递给递归函数的变量。尾递归比线性递归多一个参数，这个参数是上一次调用函数得到的结果；所以，尾递归每次调用都在收集结果，避免了线性递归不收集结果只能依次展开消耗内存的坏处。
2.3、举例
2.3.1、用不同方法计算斐波那契数列第n项的和
//方法1：最直观的递归实现(树形递归)，栈空间消耗极大，不推荐使用
function fo(n) {
if (n < 3) {
return 1;
}else{
return fo(n - 1) + fo(n - 2);
}
}//方法2：更高效的递归实现(线形递归)
function fo(first, second,n) {
if (n < 3) {
return 1;
}else{
return first + fo(second, first+second,n);
}
}//方法3：尾递归
function fo(first, second, n) {
if (n < 3) {
return second;
}else{
return fo(second, first + second, n - 1);
}
}//方法4：迭代
function fo(n) {
int first = 1;
int second = 1;
int sum = 0;
if (n < 3) {
return 1;
}else{
for( int i = 3; i <= n; i++) {
sum = first + second;
first = second;
second = sum;
}
}
return sum;
}