递归调用/非递归调用

我们都知道，很多算法，都是用递归实现的。当然它们同时也是可以用非递归来实现。

一般我们在对二叉树进行遍历的时候，还有求斐波那契数的时候，递归是非常简单的。代码容易懂，好实现。

但是递归的时候，有一个问题，就是需要压栈。为什么要压栈呢？因为当我在函数内部调用自身的时候，要中断当前的操作继续跳转到下一次的实现，而当前运行的状态要保存起来。所以就把当前状态进行压栈，等到运行到递归条件结束的时候，再弹栈。

所以递归就是需要空间的！

运行时间比较

下面我用比较简单的算法，来比较一下递归和非递归的在运行时间上的比较。

首先看下面的代码：

//
//  main.cpp
//  Euclidean
//
//  Created by Alps on 15/3/28.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include <iostream>
#include <time.h>

using namespace std;

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万次。不算多，也差不多够了。

贴上结果：

3516.000000
4077.000000
Program ended with exit code: 0

可以看到了，递归的方法时间：3516ms而递归的方法4077ms。

那是不是就是递归的方法一定比非递归快呢？
个人觉得不一定。
为什么呢？因为我觉得可能是编辑器有优化，所以速度更快。而且我自己测试的时候，只测试了几种最常见的。

结论

所以这里的结论是：

非递归并不会一定比递归快。

但是非递归确实不需要栈空间使用。

位运算与乘除法

位运算比较简单，一般就是 与或非( & | ~ )，还有就是异或( ^ ) 最后是 位移 ( >> << )这两个操作。

因为和乘除法比较，这里就只用>> <<这两个操作。

看下面代码：

//
//  main.cpp
//  test
//
//  Created by Alps on 14-10-7.
//  Copyright (c) 2014年 chen. All rights reserved.
//
#include <iostream>
#include <time.h>

using namespace std;

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 因为我没看过编译之后的代码，各位见谅。等我看到了之后再贴上来说详细为什么。

但是在除法中，就很明显了，因为位运算要快上很多。

乘法是比位运算快一点点
除法是没有位运算快的

以上结论只是我这里跑的结果。