|
在这篇博客里，我将以计算斐波那契数列指定位置的数为例介绍递归、迭代与动态规划。首先我们得弄清楚这三者的定义。 递归——程序调用自身,也就是函数自己调用自己。递归通常从顶部将问题分解，通过解决掉所有分解出来的小问题，来解决整个问题； 迭代——利用变量的原值推算出变量的一个新值。递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换； 动态规划——通常与递归相反，其从底部开始解决问题。将所有小问题解决掉，进而解决的整个问题。 下面我们以斐波那契数列为例演示这三种算法。 斐波那契数列的长相是酱紫的： 0，1，1，2，3，5，8，13，21，34，55 数学定义上的斐波那契数列没有最开始的0，也就是说其第一位应该是从上面的数列的第一个1开始，但为了更好的揭示斐波那契数列的规律，我们设其第0位为0，可以看出，除了第0，1位以外斐波那契数列的其他位上的数都是前两项之和。 现在用递归计算指定位置上的数
function recurFib(n){
if(n-1){
return n;
}else{
return recurFib(n-1)+recurFib(n-2);
}
}
为了方便展示结果，三种算法我们都以下面的方式在控制台中输出结果
document.querySelector("#recursion").onclick=function(){
//获取输入框的值
var fibonacci=document.querySelector("#fibonacci").value;
var start=new Date().getTime();
console.log(recurFib(fibonacci));
var stop=new Date().getTime();
console.log("递归用时:"+(stop-start)+"毫秒");
};
可以看到，在使用递归时，recurFib函数内部存在调用自身的部分，而且我们是把recurFib(n)分解为recurFib(n-1)，recurFib(n-2)，也就是把大问题分解为若干个小问题。 接下来我们试着用迭代
function iterFib(n){
if(n-1){
return n;
}else{
var result=0,a=0,b=1;
for(var i=2;i |