いろんな方法でフィボナッチ数列を書いてみた(Javascriptで)
私がプログラミングを始めた頃にいろいろ教えてくれた人がいて、その人は面接でフィボナッチ数列を書けと言われてうまく書けなかったらしいですが、受かったらしいです。
と、いうことで、フィボナッチ数列の第n項をいろいんなパターンで求めていきたいと思います。
フィボナッチ数列を計算することが目的というよりも、フィボナッチ数列を題材にJavascriptでいろんな計算手法を試してみたという感じの記事です。
本記事は手法をリストすることが主目的なので、各手法に関してある程度の説明はしますが詳しくはしません。また、どれが速いか(計算量)についても基本触れません。
では、本題に入ります。
forループ
配列を用意してi項目を順番に計算していくパターン
function fibonacci(n) {
const fib = [0, 1];
for (let i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
console.log(fibonacci(10)); // 55
２つの変数を用意し直近の２つの値だけを保持しながら順に計算していくパターン。
tempという変数を用意して、値を入れ替える(スワップ)テクニックはたびたび目にします。
function fibonacci(n) {
let a = 0,
b = 1;
for (let i = 2; i <= n; i++) {
const temp = a + b;
a = b;
b = temp;
}
return n === 0 ? a : b;
}
console.log(fibonacci(10)); // 55
ちなみに、以下のように分割代入を使うとシンプルに書けます。
for (let i = 2; i <= n; i++) {
[a, b] = [b, a + b];
}
whileループ
上記のforで書いたものを単純にwhileにしています。
function fibonacci(n) {
const fib = [0, 1];
let i = 2;
while (i <= n) {
fib[i] = fib[i - 1] + fib[i - 2];
i++;
}
return fib[n];
}
console.log(fibonacci(10)); // 55
function fibonacci(n) {
let a = 0,
b = 1;
let i = 2;
while (i <= n) {
const temp = a + b;
a = b;
b = temp;
i++;
}
return n === 0 ? a : b;
}
console.log(fibonacci(10)); // 55
ジェネレータ
ジェネレータの説明は割愛します。以下の記事等を参考にされると良いかと思います。
function* fibonacciGenerator() {
let a = 0,
b = 1;
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
function fibonacci(n) {
const gen = fibonacciGenerator();
let result;
for (let i = 0; i <= n; i++) {
result = gen.next().value;
}
return result;
}
console.log(fibonacci(10)); // 55
せっかくgeneratorを使っているので、for-ofを使ってみます。
function fibonacci(n) {
const gen = fibonacciGenerator();
let result = 0;
let count = 0;
for (const value of gen) {
if (count === n) {
result = value;
break;
}
count++;
}
return result;
}
console.log(fibonacci(10)); // 55
再帰(recursion)
漸化式f(n) = f(n-1) + f(n-2)をそのまま実装する感じです。
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(10)); // 55
シンプルに書けますが、nを大きくしていくと、処理が一気に重くなっていきます。nが50くらいでもかなり時間がかかります。
以下の図のようにnが大きくなっていくと、計算量が指数関数的に増えていってしまうからです。1つの項を計算するためには２つの項の計算が必要で、その２つの項に対してそれぞれ２つずつ項の計算が必要になる 1 -> 2 -> 2^2 -> 2^3 -> 2^4....と2の累乗で増えていきます。
出典：qiita - フィボナッチ数列は再帰関数の題材として適切なのか
この図を見ると、この枝分かれの中に同じ項が何度も登場している事に気づきます。
上記のコードだと同じ項が出てくるたびに、同じ計算を何度も行います。
それだと効率が悪すぎるので、一度計算したものは記録しておくという「メモ化」という手法があります。
メモ化再帰(memoized recursion)
第i項の値fibonacci(i)を計算したらmemo[i]に保存しておいて、第i項目の値が必要な際はmemo[i]を返すことで、枝分かれの連鎖を断ち切ります。
この方法でやると、先ほどは50項目でも時間がかかったのに、100項目でもすぐに求まります。
function fibonacci(n, memo = {}) {
if (n <= 1) {
return n;
}
if (memo[n]) return memo[n];
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
console.log(fibonacci(10)); // 55
これで再帰を使った手法の問題はすべて解決しているかというと、まだ問題はあります。
このメモ化再帰のコードで第20,000項目を求めようとするとどうなるでしょうか。
(実行環境にもよるかと思いますが)RangeError: Maximum call stack size exceeded となります。
有名なスタックオーバーフローというやつです。
スタックオーバーフローについて簡単に説明します。
Call stack (コールスタック)というものが関係します。
このリンク先の説明を参考にしつつ、100項目(f(100))を求める処理順を書いてみると以下のような感じになるかと思います。
f(100)を「実行」 -> f(99)を「積む」
f(99)を「実行」する中で -> f(98)を「積む」
f(98)を「実行」する中で -> f(97)を「積む」
...
f(3)を「実行」する中で -> f(2)を「積む」
f(2)を「実行」する中で -> f(1)を「積む」
f(1)を「実行」 -> 1を返す（スタックから取り除く）
f(0)を「実行」 -> 0を返す（スタックから取り除く）
f(2)が返ってくる
f(3)が返ってくる
f(98)が返ってくる
f(99)が返ってくる
f(100)が返ってくる
これが、f(20000)だと、20000個くらいひたすらコールスタックに積まれ続けるわけですが、このコールスタックには上限があって、それは環境によるのですが、それを超えてしまうと、スタックオーバーフローというエラーになります。
これにも対策というか、以下の記事を発見しました。 ジェネレータ関数と自前のコールスタックの組み合わせによってコードとして再帰の形を維持しながら、スタックオーバーフローを起こさないような仕組みを構築している記事です。
(ちなみに再帰処理のスタックオーバーフローを解決する方法としては、トランポリンという手法が有名かと思いますが、それについては後で触れます。)
なお、リンク先のrunRecursive()についてのコードは少し書き換えています。
(記事の註1に、「callerは常に今のスタックフレームの1つ前を指していますからこれは不要かもしれません」とありますが、callerを使わず書いてみました)
function runRecursive(func, ...args) {
const callStack = [];
callStack.push({
iterator: func(...args),
lastReturnValue: null,
});
while (callStack.length > 0) {
const stackFrame = callStack[callStack.length - 1];
const { iterator, lastReturnValue } = stackFrame;
const { value, done } = iterator.next(lastReturnValue);
if (done) {
callStack.pop();
if (callStack.length === 0) {
return value;
}
callStack[callStack.length - 1].lastReturnValue = value;
} else {
callStack.push({
iterator: func(...value),
lastReturnValue: null,
});
}
}
}
function* fibonacciMemoGenerator(n, memo = {}) {
if (n in memo) {
return memo[n];
}
if (n <= 1) {
return n;
} else {
memo[n] = (yield [n - 1, memo]) + (yield [n - 2, memo]);
return memo[n];
}
}
const result = runRecursive(fibonacciMemoGenerator, 2000); //Infinity
console.log(result);
おまけですが、コールスタックに関数が積まれていく様子は、JS Visualizer 9000 (イベントループのビジュアライズで有名)で確認してみると良いかもしれません。
末尾再帰
このような再帰の書き方もあります。
この書き方は末尾再帰と呼ばれる書き方で、たとえば、この記事等を参考されると良いかと思います。
'use strict'
function fibonacci(n, a = 0, b = 1) {
if (n === 0) return a;
return fibonacci(n - 1, b, a + b);
}
console.log(fibonacci(10)); //55
この書き方をすることでスタックオーバーフローを防げる場合があります。
場合がある、というのは、末尾呼び出し最適化(tail call optimization)は利用できる環境が限られているからです。現時点ではsafariのみのようです。
末尾再起が利用できない場合でも、以下の書き方でスタックオーバーフローが起きないようにする方法もあります。トランポリン(trampoline)という方法です。
トランポリン(trampoline)
トランポリンについては以下を参考にされると良いかと思います。
// トランポリン関数
function trampoline(fn) {
return function (...args) {
let result = fn(...args);
while (typeof result === 'function') {
result = result();
}
return result;
};
}
function fibonacciTrampoline(n, a = 0, b = 1) {
if (n === 0) return a;
return () => fibonacciTrampoline(n - 1, b, a + b);
}
const fibonacci = trampoline(fibonacciTrampoline);
console.log(fibonacci(10));
DP(Dynamic Programing)
以下の記事が参考になるかと思います。(コードはc++ですが)
function fibonacci(n) {
const dp = new Array(n + 1).fill(0);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(fibonacci(10));
以上となります。
間違い等あれば、ご指摘いただけるとありがたいです。
Discussion