首页 > 代码库 > 剑指offer (9) 递归和迭代 斐波那契数列

剑指offer (9) 递归和迭代 斐波那契数列

通常基于递归实现的代码比基于循环实现的代码要简洁很多

比如 二叉树遍历以及 二叉树的许多操作

 

递归由于是函数调用自身,每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量

而每个进程的栈容量是有限的,当递归调用的层级太多时,就会导致 调用栈溢出

 

递归有时伴随大量重复的计算, 二叉树遍历的递归操作不存在重复计算,因为每个结点的左右子树是严格区分开的

 

例如求解 斐波那契数列:

 

解题分析

 int fib(int n) {
        assert(n >= 0);
        int prevTwo = 0;
        int prevOne = 1;
        int cur = 1;
        for (int i = 1; i <= n; ++i) {
            prevOne = cur;
            cur = prevOne + prevTwo;
            prevTwo = prevOne;
        }
        return cur;
    }

 

int fib(int n) {
        assert(n >= 0);
        double s = sqrt(5);
        return floor((pow((1+s)/2, n+1) - pow((1-s)/2, n+1)) / s);
    }

 

相关题目:

用 2×1 的小矩形横着或者竖着 去覆盖 更大矩形

例如:用 8个 2×1的小矩形 无重叠覆盖 2×8的大矩形

 

 

 

我们将 2×n的覆盖方法表示为 f(n) 

用第一个2×1小矩形去 覆盖最左边时有两个选择:

横着:两个 2×1横着放,这样就剩下 2×(n-2)待覆盖 ,即 f(n-2)

竖着:一个 2×1竖着放,这样就剩下 2×(n-1)待覆盖,即 f(n-1)

即 f(n) = f(n-2) + f(n-1) ,且 f(0) = 0, f(1) = 1 , f(2) = 2