うどんとそばならうどん派、どうもswitchです。
さて、突然なのですが、以下のコードの意味がわかりますでしょうか?
function fib(n) {
return n < 2 ? n : fib(n - 2) + fib(n - 1);
}
わかっていただけた場合は、この記事を読む必要はないと思います。
ここから先は、上記のコードがわからない方向けになります。
?の文字の意味がわからない方も、ぜひ読んで行ってくださいねー。
?:の意味 〜条件演算子〜
JavaScriptで度々見かけるこの?:の記号。
わからなかったけど、調べてもうまくヒットしなかった・・・という方もいるのではないでしょうか(私がそうです)。
こちらの記号、条件(三項)演算子と言いまして、if文のショートカットによく使われます。
構文は以下の通りになります。⬇︎
「条件式 ? 条件式がtrueの時に実行する式 : falseの時に実行する式」
最初のコードでは、
nが2より小さい時にはnをそのまま返し、そうではない場合は 「fib(n - 2) + fib(n - 1); 」の式を実行する、と言う意味になります。
それでは本題、このコード→fib(n - 2) + fib(n - 1); の解説をやっていきましょう。
フィボナッチ数列のアルゴリズム
最初のコードがわからないと言う方は、一度以下のようなコードを思いついたことがあるのではないでしょうか。
var end = 5;
var count = 0;
var result = 0;
var a = 1;b = 1;c = 0;
console.log(fib(a,b,c,count,end - 2));
function fib (a,b,c,co,end) {
a = b + c;
c = b;
b = a;
if (co == end) return a;
else return fib(a,b,c,co = co + 1,end);
}
これは三つの変数を足しあったり中身をコピーしたりしてフィボナッチ数列を作る方法の一つですが、こちらの方法だと、数列の一つ前と二つ前の数を変数に記録しています。
だから、数列の先頭を新しく追加するときは、その二つの数を参照することで求められます。
しかし、以下のコード(最初のコードと同じ内容です)は、いちいち数列の一つ前、二つ前を計算し、足すという処理を行っています。
function fib(n) {
return n < 2 ? n : fib(n - 2) + fib(n - 1);
}
まだわかりにくいかと思うので、上記のコードのnに3を入れた時の挙動をシミュレーションしてみましょう!
関数実行
fib(3-2) + fib(3-1);を実行
まず、fib(3-2)を実行
3-2は1なので、fib(3-2)は1になる。・・・➀
fib(3-1)を実行
3-1は2なので、fib(2-2) + fib(2-1)
fib(2-2)を実行し、0が返ってくる。
fib(2-1)を実行し、1が返ってくる。
0+1は1なので、fib(3-1)は1になる。・・・➁
➀と➁より、1+1は2になる。
関数終了
3という小さい数字でも、4回も関数を実行しています。
いちいち二つ前と一つ前の数列を計算を計算をするというのはこういうことなのです。
例えばnに100を入れると、実行完了まで100兆年かかります。
だから、フィボナッチ数列の最適化をする方法はたくさん考案されています。
しかしここではそこについては深く触れません。検索していただければ、わかりやすい解説があると思いますので、興味のある方はどうぞー。
この記事を通してコードを理解していただけたのなら幸いです。
それでは! ノシ