例如 fn = fn-1 + fn-2;
如果按照公式的表面来看 得出递归的公式：f(n) = f(n-1) + f(n-2);
如果想要实现这样的递归至少需要两个栈空间
编译器有个特性如果递归调用是最后执行的，执行之后原函数不需要对递归的结果做任何操作，
那么这个递归调用不会另外开一个栈空间，他会覆盖原来的栈空间，这样就少用了很多的栈空间防止栈溢出
那么斐波那契递归要怎么优化呢？
fn = f(n-1,res1,res2);
这个n可以看作运算的次数相关数，比如算f5是不是要算5次的加法 (这里假设从f0开始）
res1,res2代表算当前的fb-2,fb-1 这个b和n不一样
这种写法其实和递推计算的过程就是一样的了
```
#include <bits/stdc++.h>
using namespace std;
int f(int n,int res1,int res2){
if(n == 0){
return res1;
}
return f(n-1,res2,res1+res2);
}
int main(){
int f0 = 0;
int f1 = 1;
cout << f(5,f0,f1) << endl; // 1 1 2 3 5
}
```
那么面试常常会问 快排的优化
快排尾递归优化。。。
我想说下面这种尾递归博客里面烂大街的方式真的优化了么？
不管去不去掉都要保存当前的环境
但他确实优化了！！！
```
#include <bits/stdc++.h>
using namespace std;
int a[] = {3,4,2,1,2};
int sz = 4;
int partition1(int low,int high){
int pivot = a[low];
while(low < high){
while(low < high && a[high] >= pivot) high--;
a[low] = a[high];
while(low < high && a[low] <= pivot) low++;
a[high] = a[low];
}
a[low] = pivot;
return low;
}
void quicksort(int low,int high){
int index;
while(low < high){ //if换成了while
int pivot = partition1(low,high);
quicksort(low,pivot-1);
// quicksort(pivot+1,high);
low = pivot+1; //优化部分
}
}
int main(){
quicksort(0,sz);
for(int i = 0;i <= sz;++i){
cout << a[i] << endl;
}
}
```
现在我来说下原因，这个可以看成一颗二叉树，原来是把二叉树左分支和右分支分别去处理，而当前的环境依然保留，
而优化的方式优化的地方是他把当前的环境变成了右分支，就是这里他这样的作法相当于擦掉了右节点，压缩了一个节点的深度，
那么就缩小了最大的栈深度
这是一个模拟尾递归的过程，而不是真正意义上的利用编译器的尾递归优化特性
