javascriptでフィボナッチ数

一般的な書き方。

var fibo = function(n){
  if(n===0){
    return 0;
  }else if(n===1){
    return 1;
  }else{
    return fibo(n-1)+fibo(n-2);
  }
};

スタックオーバーフローになる。

状態値をもたせる方法（メモ化）。

var fibo = function(n,a,b){
  if(n===0){
    return 0;
  } else if(n===1){
    return a;
  } else{
    return fibo(n-1,a+b,a);
  }
};

a=1, b=0 と渡す

fibo(10,1,0) // 55

fibo(100,1,0) // 354224848179262000000

a,bという状態値をクロージャに持たせる方法。

var fibo = function(n){
  if(n){
    var a=1,b=0;
    var innerFunc = function(n,a,b){
      if(n===0){
        return 0;
      } else if(n===1){
        return a;
      } else {
        return innerFunc(n-1,a+b,a);
      }
    };
    return innerFunc(n,a,b);
  }
};

fibo(10) // 55

fibo(100) // 354224848179262000000

上記では、nが空の場合、処理をエスケープしている。

エスケープせずに以下の通り書くと、fibo() と引数を空にした場合に、スタックオーバーフローになる。

var fibo = function(n){
  var a=1,b=0;
  var innerFunc = function(n,a,b){
    if(n===0){
      return 0;
    } else if(n===1){
      return a;
    } else {
      return innerFunc(n-1,a+b,a);
    }
  };
  return innerFunc(n,a,b);
};