首页 > 代码库 > 剑指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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。