C/Java/Python/Objective-C多种编程语言实现递归计算

递归下降语法分析器

• 类型：源码相关大小：34KB语言：中文 评分：5.0
• 标签：

立即下载

同样的算法多种编程语言在Mac的OS X上跑会是个什么情况呢？

于是写了四种语言的斐波那契数列实现：C、Java、Python、Objective-C，而且都采用了效率最差耗时最长的递归实现，不使用其他数据结构或公式，这样对比起来更容易一些，如果使用迭代方式的话，执行时间太短很难比较。

第一轮测试不做任何优化，第二轮分别做一些编译和环境的调优处理，然后再看一下结果。代码如下：

c语言，使用函数实现递归计算

#include <stdio.h>

long fib(int n){
    if (n < 2)
        return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    printf( "fib= %ld", fib(40) );
    return 0;
}

Java，使用静态方法实现递归计算

public class fib {

    public static long jfib(int n ){
        if (n < 2)
            return n;
        return jfib(n - 1) + jfib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println( jfib( 40 ) );
    }
}

Python，使用函数实现递归计算

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print fib(40) 

Objective-C，使用block实现递归计算

#import <Foundation/Foundation.h>

int main(int argc, const char * argv[])
{
    @autoreleasepool {
        
        long (^__block fib)(long) = ^(long num){
            if ( num < 2 )
                return num;
            return fib(num-1) + fib(num-2);
        };
        
        NSLog(@"Fib: %ld", fib(40) );
        
    }
    return 0;
}

基本的测试环境：

C语言：i686-apple-darwin11-llvm-gcc-4.2

Java：java version "1.6.0_37"，HotSpot(TM) 64-Bit

Python：Python 2.7.2 with GCC 4.2.1

Pypy：PyPy 1.9.0 with GCC 4.2.1

Objective-C：2.0 with LLVM 4.1

使用time命令计算执行时间，例如time python fib.py

直接编译运行的结果还是比较让人吃惊的：

C：1 秒

Java：0.63 秒

Python：45.79 秒

Objective-C：1.3 秒

结果：Java > C > Objective-C > Python

这个结果让人感到，Java真的不慢，动态语言有点慢。

第二轮测试，针对C程序，使用gcc -O进行优化编译；针对Python，使用pypy替换原生的python环境，针对Objective-C，设置优化Level为Fastest，结果如下：

C：0.35 秒

Java：0.63 秒

Python：4.96 秒

Objective-C：1.04 秒

结果：C > Java > Objective-C > Python

这个结果告诉我们，C还是最快的，pypy对python的优化处理还是非常明显的。 

以上数据是在OS X平台上的、性能比例放大的测试结果，在实际应用中，如果针对不同场景采用了正确的算法，差距就不会有这么大，比如我们用迭代方式改写一下python的实现，如下：

def fib(n):
    if n < 2:
        return n
    a1 = a2 = a3 = 1
    while n>2:
        n -= 1
        a3=a1+a2
        a1=a2
        a2=a3

    return a3

print fib(40)

这时无论使用Python编译执行还是Pypy执行，基本都是0.02秒左右，没有太大差别。以上代码的执行结果是102334155，有兴趣的可以在自己的机器上试试。

声明：

1、以上代码仅供参考娱乐，实际应用中如果使用斐波那契数列，绝对不要使用递归调用的方式，迭代法应该是不错的选择。

2、数据量加大可能会有不同的结果，有兴趣的可以尝试下。

实验完成，希望对大家有参考。