两种不同的递归方式

Question

我用两种不同的方式计算斐波那那排.为什么fib1的执行时间比fib2长得多？

public class RecursionTest {

    @Test
    public void fib1() {
        long t = System.currentTimeMillis();

        long fib = fib1(47);

        System.out.println(fib + "  Completed fib1 in:" + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();

        fib = fib2(47);

        System.out.println(fib + "  Completed fib2 in:" + (System.currentTimeMillis() - t));

    }


    long fib1(int n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            return fib1(n - 1) + fib1(n - 2);
        }
    }


    long fib2(int n) {
        return n == 0 ? 0 : fib2x(n, 0, 1);
    }

    long fib2x(int n, long p0, long p1) {
        return n == 1 ? p1 : fib2x(n - 1, p1, p0 + p1);
    }
}

输出:

2971215073  Completed fib1 in:17414
2971215073  Completed fib2 in:0

Answer 1

因为两种算法完全不同.让我用fib(5)告诉你.

如果你调用fib1(5),它在内部调用fib1(4)和fib1(3),让我们用树可视化:

    fib(5)
  /       \
fib(4)   fib(3)

现在,fib(4)内部称为fib(3)和fib(2).

所以现在我们有了这个:

           fib(5)
          /       \
    fib(4)       fib(3)
    /  \          /  \
fib(3) fib(2)  fib(2) fib(1)

我认为到目前为止,这是非常明显的,你应该能够填补其余部分.

编辑:你应该注意的另一件事是,它实际上必须多次执行相同的caclculation.在这张图片中,fib(2)和fib(3)都被称为多次.如果起始数字更大,这会变得更糟./编辑

现在,我们来看看fib2(5).你用0调用它,它返回0.否则,它调用fib2x(n,0,1)所以,我们调用fib2x(5,0,1).fib2x(n,0,1)现在内部调用fib2x(n-1,p1,p0 + p1),依此类推.所以,让我们看看:

        
fib2x(5, 0,1) => fib2x(4, 1,1) => fib2x(3, 1, 2) => fib2x(2, 2, 3) => fib2x(1, 3, 5)

到那时,它已达到返回条件并返回5.

因此,您的算法完全不同.第一个是递归地从顶部到底部工作.第二个从1开始,然后继续前进.实际上,它更迭代然后递归(它可能是递归写入你的).它保留已经计算的值而不是丢弃它们,因此需要调用更少的计算.

Answer 2

原因是两种算法具有不同的运行时复杂性:

• fib1在Ο(2 ⁿ)
• fib2在Ο(n)