递归调用/非递归调用
我们都知道，很多算法，都是用递归实现的。当然它们同时也是可以用非递归来实现。
一般我们在对二叉树进行遍历的时候，还有求斐波那契数的时候，递归是非常简单的。代码容易懂，好实现。
但是递归的时候，有一个问题，就是需要压栈。为什么要压栈呢？因为当我在函数内部调用自身的时候，，要中断当前的操作继续跳转到下一次的实现，而当前运行的状态要保存起来。所以就把当前状态进行压栈，等到运行到递归条件结束的时候，再弹栈。
所以递归就是需要空间的！
运行时间比较
下面我用比较简单的算法，来比较一下递归和非递归的在运行时间上的比较。
首先看下面的代码：
;int gcd(int a, int b){if (a%b == 0) {return b;}return gcd(b, a%b);}int gcd_t(int a, int b){int temp = a;while(a%b != 0){a = b;b = temp%b;temp = a;}return b;}int MinMultiple(int a, int b){return (a*b)/gcd(a, b);}int main(int argc, const char * argv[]) {int a = 14, b = 18;int i = 100000;double start = (double)clock();for (int j = 0; j < i; j++) {gcd(a,b);}double end = (double)clock();printf(“%f\n”,end – start);start = (double)clock();for (int j = 0; j < i; j++) {gcd_t(a,b);}end = (double)clock();printf(“%f\n”,end – start);return 0;}
这里的gcd()相比都很熟悉，就是欧几里得算法。不懂这个算法的可以看我上一篇博客：欧几里得算法(辗转相除法)
在这个代码里，我分别对递归方法和非递归方法调用了10万次。不算多，也差不多够了。
贴上结果：
ended with exit code: 0
可以看到了，递归的方法时间：3516ms而递归的方法4077ms。
那是不是就是递归的方法一定比非递归快呢？ 个人觉得不一定。 为什么呢？因为我觉得可能是编辑器有优化，所以速度更快。而且我自己测试的时候，只测试了几种最常见的。
结论
所以这里的结论是：
非递归并不会一定比递归快。
但是非递归确实不需要栈空间使用。
位运算与乘除法
位运算比较简单，一般就是 与或非( & | ~ )，还有就是异或( ^ ) 最后是 位移 ( >> << )这两个操作。
因为和乘除法比较，这里就只用>> <<这两个操作。
看下面代码：
;int main(int argc, char**argv){int a = 1234567;int time = 100000;double start = (double)clock();for(int i=0;i<time;++i){a = a << 1;}double end = (double)clock();printf(“==========\n bit operate: %f\n==========\n”,end – start);a = 1234567;start = (double)clock();for(int i= 0;i<time;++i){a = a * 2;}end = (double)clock();printf(“==========\n multiple operate: %f\n==========\n”,end – start);start = (double)clock();for(int i=0;i<time;++i){a = a >> 1;}end = (double)clock();printf(“==========\n bit operate: %f\n==========\n”,end – start);a = 1234567;start = (double)clock();for(int i= 0;i<time;++i){a = a / 2;}end = (double)clock();printf(“==========\n division operate: %f\n==========\n”,end – start);return 0;}
这个大家可以很容易的看出来我所写的目的，就是把位运算和乘除法操作的时间输出来。
结果如下：
/Users/alps/Documents/code/c/test/test >./main========== bit operate: 272.000000==================== multiple operate: 268.000000==================== bit operate: 277.000000==================== division operate: 1156.000000==========结论
可以看到，乘法中，10w次，其实是乘法比位运算快一点点。这个我个人的猜测是编译器在底层对乘法进行了优化。
But!! 我不确定 TT 因为我没看过编译之后的代码，各位见谅。等我看到了之后再贴上来说详细为什么。
但是在除法中，就很明显了，因为位运算要快上很多。
乘法是比位运算快一点点 除法是没有位运算快的
以上结论只是我这里跑的结果。
每天告诉自己一次，我真的很不错
