《剑指Offer系列》斐波那契数列的问题

coding 斐波那契数列

见书73页。

此处重新复习了下递归和迭代的不同。

递归写起来比较简洁。但是，因为递归是不断调用函数，调用函数要入栈出栈一些局部变量、函数返回地址等。这样上下文的切换，会带来过多的时间开销。而且会带来另一个问题：栈溢出。因此相同条件下会比循环的效率低很多。

斐波那契数列的递归版

public class Fib {
        public static int fb(int n){
            if(n  <= 0) //注意小于0的情况
                return 0;
            if(n == 1) //递归出口
                return 1;
            return fb(n - 1) + fb(n - 2);
        }
}

这种写法会造成很多函数的重复调用，性能很低。实际上可以把中间结果保存起来，通过查取而不是继续调用函数迭代的方式解决。

迭代版

public class Fib {
    public static long fb(int n){
        if(n <= 0)
          return 0;
        if(n == 1)
          return 1;
        long pre = 0;
        long cur = 1;
        for(int i = 2; i <= n; i++) {
            long tmp = pre + cur;
            pre = cur;
            cur = tmp;
        }
        return cur;
    } 
}

注意青蛙跳台阶的问题，就是用斐波那契数列来解决的。另有方块覆盖的问题，也是斐波那契数列来解决。