斐波那契數列與IE9

百度什麼都知道：當然也包括斐波那契(Fibonacci)數列

在一般算法教材中，把Fib數列都是當做遞歸的經典示例來講解的：

javascript的寫法如下： 

//遞歸法(計算到fib(40)時浏覽器就挂掉了)
function fib(n){  
  if (n<=2){
    return 1;
  } 
  return fib(n-1) + fib(n-2);
}
      

在IE9以下的IE浏覽器中，跑到fib(40)基本上浏覽器就罷工了，比如：

for(var j=1;j<=40;j++){
  document.write("fib(" + j +  ")=" + fib(j) + "<br />");
}
      

但是在IE9下，居然能挺過來，看來IE9對javascript引擎的優化确實效果不錯

當然，這個數列除了遞歸，還有其它非遞歸的解法，一并貼在這裡收錄一下：

//遞歸法(計算到fib(40)時浏覽器就挂掉了)
function fib(n){  
  if (n<=2){
    return 1;
  } 
  return fib(n-1) + fib(n-2);
}


for(var j=1;j<=40;j++){
  document.write("fib(" + j +  ")=" + fib(j) + "<br />");
}


document.write("<hr />");

//非遞歸法1
function fib2(n){
  var temp=i=f1=f2=1; 
  if (n<=2){
    return 1;
  }
  else
  {
    for(i=3;i<=n;i++){
      temp = f1+f2;
      f2=f1;
      f1=temp;
    }
    return temp;
  }
}

//測試
for(j=1;j<=40;j++){
  document.write("fib2(" + j +  ")=" + fib2(j) + "<br />");
}

document.write("<hr />");

//非遞歸法2
function fib3(n){
  if (n<=2){
    return 1;
  }
  var x=0,y=1;
  for (var j=1;j<n;j++) {
    y = x + y;
    x = y - x;  
  } 
  return y;
}

//測試
for(j=1;j<=40;j++){
  document.write("fib3(" + j +  ")=" + fib3(j) + "<br />");
}
      

作者：菩提樹下的楊過