递归处理斐波那契数时的低效率

现在的位置: 首页 > 综合 > 正文

递归处理斐波那契数时的低效率

2018年08月13日 ⁄ 综合 ⁄ 共 1991字 ⁄ 字号小中大 ⁄ 评论关闭

某些递归解法的效率如此之低下，以致于必须避免。

例：斐波那契数（Fibonacci）早在13世纪，数学家莱昂纳多斐波那契（Leonardo Fibonacci）就提出了一个用以模拟一对兔子后代数目的整数序列，这些后来称为斐波那契序列（Fibonacci sequence）的数名人惊讶的出现在许多应用中。

序列为：1,1,2,3,5,8,13....

公式为：F(n) = F(n-1) + F(n-2)

使用递归算法将造成大量的重复计算，而它每层的递归会形成反向的Fibonacci序列。

如下如：

操作----------计算次数

Fib(5) 1

Fib(4) 1

Fib(3) 2

Fib(2) 3

Fib(1) 5

而Fib(0)等于Fib(2)的计算次数

很明显，此时使用递归算法的效率要低得多。

以下是我用Java的编写的程序：

/**
 * f(n)=f(n-1)+f(n-2),使用递归算法将产生级差的效率
 * @author scorpio
 */
public class DiGv {
    private static final int NUMBER = 43;
    /** 采用递归实现 */
    private static int fibonacci_1(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return fibonacci_1(n - 1) + fibonacci_1(n - 2);
        }
    }
    /** 采用循环实现,n<1返回0 */
    private static int fibonacci_2(int n) {
        int sum = 0;
        if (n > 0) {
            sum = 1;
            int count = 0;
            for (int temp = 0, t = 0; n != count; ++count) {
                t = sum;
                sum += temp;
                temp = t;
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        long startTime = 0;
        long endTime = 0;
        int result = 0;
        System.out.println("递归的拙劣算法/n---------------------/n");
        System.out.println("使用递归算法：");
        startTime = System.currentTimeMillis();
        result = DiGv.fibonacci_1(NUMBER);
        endTime = System.currentTimeMillis();
        System.out.println("时间差：" + (endTime - startTime) + "/t计算结果：" + result);
        System.out.println();
        System.out.println("使用非递归算法：");
        startTime = System.currentTimeMillis();
        result = DiGv.fibonacci_2(NUMBER);
        endTime = System.currentTimeMillis();
        System.out.println("时间差：" + (endTime - startTime) + "/t计算结果：" + result);
    }
}