おぼえておくという工夫

工夫には、別の角度がある

ここまでの工夫は、ぜんぶ「くらべる順番」の工夫でした。半分に割ってからくらべる、そろえてから半分を捨てる——順番を変えるだけで、回数は劇的に減りました。

今日の工夫は、まったく別の角度から来ます。同じ計算を、二度しない。 それだけです。

そして今日は、実験室の再生ボタンではなく、コース1で手に入れたJavaScriptを使います。手順を自分の手で書きかえて、回数の変わりかたを自分の目で確かめるためです。

フィボナッチという数列

題材は、0、1、1、2、3、5、8、13、21……という数列です。決まりはひとつだけ——前の2つを足すと、次の数。13世紀のイタリアの数学者フィボナッチの名で呼ばれ、ひまわりの種のうずまきにも顔を出す、有名な数列です。

「n番目の数」の決まりを、曖昧さのないことばにするとこうなります。

• 0番目は 0、1番目は 1
• 2番目から先は、「n−1番目」と「n−2番目」の和

この決まりを、そのままJavaScriptにします。コース1で出てこなかった表記が2つあるので、まず動かしてから、下で解剖しましょう。

let kaisu = 0;

function fib(n) {
  kaisu = kaisu + 1;
  if (n <= 1) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

console.log("こたえ: " + fib(10));
console.log("よばれた回数: " + kaisu);

新しい表記の1つめは if (条件) { } ——にわ語で学んだ「もしも」の、JavaScriptでの書きかたです。条件が成り立つときだけ、中の文が実行されます。

2つめは return です。コース1の関数は console.log で「言う」だけでしたが、return は答えを呼んだ側に手渡して、関数を終える書きかたです。fib(10) という式が55という値になるのは、この手渡しのおかげです。

そして見慣れない光景がひとつ——fib の中で、fib 自身を呼んでいます。決まりが「前の2つの和」なのだから、書きかたもそのまま、というわけです。自分で自分を呼ぶこの書きかたは**再帰（さいき）**と呼ばれ、n <= 1 で必ず行き止まりに着くので、レッスン1の「必ず終わる」条件もちゃんと満たしています。

177回、21,891回、2,692,537回

kaisu は、コース1でやった let の付け替えです。fib が呼ばれるたびに1増える、回数を数える係を仕込んであります。

実行すると、こたえは55、よばれた回数は177回と出たはずです。10番目の数をひとつ知るために、177回。すこし多すぎる気がしませんか。

では fib(10) の10を20に、それから30に変えて、実行してみてください。

nが10増えるごとに、回数はおよそ120倍——nが1増えるごとに約1.6倍になる、指数のかたちです。レッスン6で見たどのかたちよりも急な、最悪のかたちです。35あたりまで上げると数千万回になり、この実験室は時間切れで音を上げます（こわれはしません。止まるだけです）。

なぜ、爆発するのか

プログラムにまちがいはありません。原因は手順のかたちにあります。fib(10) の最初の数歩を、ことばで追ってみましょう。

• fib(10) は、fib(9) と fib(8) を呼ぶ
• その fib(9) も、fib(8) と fib(7) を呼ぶ——この時点で fib(8) の計算が2回始まっている
• 2本の fib(8) がそれぞれ fib(7) を呼び、fib(9) のぶんとあわせて fib(7) は3回
• ……と、枝分かれのたびに、同じ枝がもう一度生える

計算のすがたは、下へ下へと枝分かれする木です。ただしふつうの木とちがって、同じ枝が何本も生えています。177回の内訳を数えると、こうなっています。

• fib(8) の計算：2回
• fib(7) の計算：3回
• fib(6) の計算：5回
• fib(5) の計算：8回
• fib(4) の計算：13回

fib(5) の答えは何度計算しても8です。それなのにこの手順は、毎回まっさらな顔で計算し直します。爆発の正体は、このくりかえされるむだです。

答えを、おぼえておく

工夫はこうです。一度計算した答えに名前をつけて、とっておく。次に同じ質問をされたら、計算せずに、とってある答えだけ返す。 この工夫をメモ化と呼びます。

メモ帳には、JavaScriptに備えつけの Map という道具を使います。動詞は3つだけです——memo.set(なまえ, 値) で書きこみ、memo.has(なまえ) で「もう書いてあるか」を確かめ、memo.get(なまえ) で読み出します。

let kaisu = 0;
const memo = new Map();

function fib(n) {
  kaisu = kaisu + 1;
  if (memo.has(n)) {
    return memo.get(n);
  }
  if (n <= 1) {
    return n;
  }
  const kotae = fib(n - 1) + fib(n - 2);
  memo.set(n, kotae);
  return kotae;
}

console.log("こたえ: " + fib(10));
console.log("よばれた回数: " + kaisu);

さっきのプログラムとの差分は、3か所だけです。

1. メモ帳を1冊、用意する（const memo = new Map();）
2. 計算を始める前に、メモを見る——書いてあれば、それを返しておしまい
3. 計算が済んだら、答えを返す前に、メモに書いておく

実行してください。こたえは同じ55のまま、よばれた回数は19回です。10を20、30に変えると——

2,692,537回が、59回になりました。nが10増えても回数は20しか増えない——爆発（指数）が、直線（比例）に変わったのです。同じ枝が二度と生えないので、木が一本道に近いかたちに刈りこまれた、と言ってもかまいません。

ただでは、ない

ここで、このコースの習慣どおり、正直に値段の話をします。メモ帳は、紙を使います。

fib(30) を終えたとき、メモには29個の答えが書きこまれています。最後に console.log(memo.size); の1行を足すと、自分で確かめられます。答えをおぼえておくぶんだけ、コンピュータの記憶の置き場が占領されるのです。

この構図、レッスン5で見たものと同じです。マージは「控えの紙」という置き場を使って速さを買っていました。メモ化も、計算の時間を、記憶の場所で買っています。この取り引きには名前があります——時間と空間のトレードオフ。速さの裏で何かを支払っているとき、その何かはたいてい場所です。

暮らしの中の「おぼえておく」

紙の辞書で同じ単語を何度も引く人は、そのページに付せんを貼ります。二度目からは、さがさずに開けるからです。これはあなたの時間を、付せんという場所で買う、人間のメモ化です。

ただし、このたとえには限界もあります。付せんだらけになった辞書は、今度は付せんをさがすのに手間どります。メモにも場所代がかかる——どこまでおぼえてどこから計算し直すかは、それ自体がひとつの選択です。

let kaisu = 0;
const memo = new Map();

function fib(n) {
  kaisu = kaisu + 1;
  if (memo.has(n)) {
    return memo.get(n);
  }
  if (n <= 1) {
    return n;
  }
  const kotae = fib(n - 1) + fib(n - 2);
  memo.set(n, kotae);
  return kotae;
}

console.log("こたえ: " + fib(10));
console.log("よばれた回数: " + kaisu);

このレッスンで分かったこと

• 今日の工夫は順番ではなく、同じ計算を二度しないこと
• 素朴な再帰のfibは、同じ枝が何度も生える木。回数は指数のかたちで爆発する（fib(30)で2,692,537回）
• メモ化：計算の前にメモを見て、計算のあとにメモに書く。それだけで爆発が直線になる（fib(30)で59回）
• ただし、メモは記憶の置き場を使う。時間と空間のトレードオフ——速さは、場所で買っている