从斐波那契数列看递归和动态规划

charles_paul 发布于2019-08-22 18:30 / 2696人阅读

摘要：大名鼎鼎的斐波那契数列，，，，，，，，使用数学归纳法可以看出其规律为。对于斐波那契数列的求解，有自顶向下的记忆化搜索递归和自下向上的迭代法，他们都使用了动态规划的思想。

大名鼎鼎的斐波那契数列：0，1，1，2，3，5，8，13，21...使用数学归纳法可以看出其规律为：f(n) = f(n-1) + f(n-2)。

递归

下面首先直接使用递归（JavaScript实现）来求解第 n 项：f(n)

// 直接使用递归
let num = 0;    // 用来记录fib函数执行次数，执行一次加一
function fib(n) {
  num ++;
  if(n === 0) {
    return 0;
  }
  if(n === 1) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

console.time("time used");
console.log(`result is: ${fib(40)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("time used");

以 n = 40 为例，这里我们记录了 fib 函数总共调用的次数以及运算总共耗时，结果如下：

可以看出，即便仅仅是计算第 40 项，fib 函数调用的次数高达3亿多次，时间是2477ms。因为每一次 fib 函数的调用都会有两个子 fib 函数调用，那么时间复杂度是 O(2^n) ，呈指数级增长，这显然不是一个好算法。怎么优化呢？以一个简单的例子画图分析一下：

上图是 n = 5 时的递归树，可以看出虚线框中 f(2) 的计算用到了三次，同样的 f(3) 的计算用到了两次，显然我们执行了非常多的重复运算。那么很自然的想到，把每一个状态的计算结果都存起来，后面遇到相同的状态就可以直接使用了。

记忆化搜索递归(自顶向下)

代码如下，这里第三行 new 了一个长度为 n+1 的数组，用于存放 f(0) 到 f(n) 这 n+1 个状态的计算结果：

// 记忆化搜索，记录每次计算的结果
let num = 0; // 用来记录fib函数执行次数，执行一次加一
let totalnum = 40;
let memory = new Array(totalnum).fill(-1);
function fib(n) {
  num++;
  if(n === 0) {
    return 0;
  }
  if(n === 1) {
    return 1;
  }
  if(memory[n] === -1) {
    memory[n] = fib(n-1) + fib(n-2);  // 如果前面已经得到，直接使用
  } 
  return memory[n];
}

console.time("timer");
console.log(`result is: ${fib(totalnum)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("timer");

同样 n = 40，结果如下：

可以看处出优化是十分可观的，记录下每一次子调用的结果，让算法复杂度从 O(2^n) 变成了 O(n)。这其实就是动态规划的思想。什么是动态规划？

Dynamic programming is when you use past knowledge to make solving a future problem easier.(动态规划是用已知项去更好的求解未知项)

Dynamic programming is a technique used to avoid computing multiple time the same subproblem in a recursive algorithm.

将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

以上是我看到的两个很好的定义。记忆化搜索递归求斐波那契数列显然是使用了动态规划的思想，并且，这是一种自顶向下的求解方式（我们没有从最基本的问题开始求解，对于 f(n) = f(n-1) + f(n-2) ，先假定 f(n-1) 和 f(n-2) 是已知的）。另外我们可以采用另一种自下向上的方式求解，即迭代，这也是一种动态规划的思想。

迭代法(自下向上)

代码如下，我们使用迭代，f(2) = f(1) + f(0),f(3) = f(2) + f(1),...，显然这是一种从基础问题开始的自下向上的解决方法：

let num = 0;
function fib(n) {
  num++;
  let memory = new Array(n);
  memory[0] = 1;
  memory[1] = 1;
  for(let i = 2; i <= n; i++) {
    memory[i] = memory[i-1] + memory[i-2];  
  }
  return memory[n];
}

console.time("timer");
console.log(`result is: ${fib(40)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("timer");

结果如下，显然使用迭代的方法复杂度也为 O(n)：

小结

动态规划就是：将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。对于斐波那契数列的求解，有自顶向下的记忆化搜索递归和自下向上的迭代法，他们都使用了动态规划的思想。

参考链接：
https://stackoverflow.com/que...

云服务器 GPU云服务器波那契数列动态规划动态规划python java动态规划代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95942.html

时间复杂度、递归、尾调用— (读文笔记)

摘要：递归算法是一种直接或者间接调用自身函数或者方法的算法。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。调用栈尾递归和手动优化尾调用就是一个函数执行的最后一步是将另外一个函数调用并返回。输出斐波那契数列的四种写法读参考文章列表算法复杂度中的O(logN)底数是多少从斐波那契数列谈谈代码的性能优化冰与火之歌：时间与空间复杂度 ...

susheng 2019-08-23 14:34 评论0 收藏0
js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0
动态规划问题（1）——斐波那契数列

摘要：动态规划有时被称为递归的相反的技术。动态规划方案通常使用一个数组来建立一张表，用于存放被分解成众多子问题的解。今天我们先从我们最熟的斐波那契数列数列开始。斐波那契数列在很多地方都会用上，我是从一个台阶问题发现的，同时知道了动态规划的解法。前段时间一直写了几个算法题目，发现有个很牛逼的算法，动态规划，虽然有的解题思路和动态规划很像，但是当时不知道其中的原理和一些通用性，接下来的几天，通...

Eminjannn 2019-08-21 11:24 评论0 收藏0
斐波那契数列求和的js方案以及优化

摘要：在上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。动态规划解决方案斐波那契数列求和除了可以用递归的方法解决，还可以用动态规划的方法解决。在codewars上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。题目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0