STAGE 8
再帰と動的計画法
同じ計算を二度しない
🎯 ミッション
素朴な再帰が遅くなる理由と、動的計画法(表に書いて使い回す)で速くなる理由を説明できるようになろう。10段までの表を埋め、確認クイズに全問正解すれば合格。
未達成

ねこ博士
宝箱のある塔の階段は10段。1回に1段か2段ずつ上れるとき、上り方は何通りあるか。小さい段数で数えてごらん。

うさ美
1段なら「1」の1通り。2段なら「1+1」と「2」の2通り。3段なら「1+1+1」「1+2」「2+1」の3通り。

ねこ博士
一つ一つ数えると大変になるので、考え方を変えよう。n 段目に着く直前、最後の1回は何段上った?

うさ美
1段か2段のどちらかです。最後に1段上ったなら、その前は n−1 段目にいた。2段なら n−2 段目にいた。……だから、n 段目への上り方は、n−1 段目への上り方と、n−2 段目への上り方の合計。
ways(n) = ways(n−1) + ways(n−2) (ways(0) = 1、ways(1) = 1 とする)
ways(2) = 1+1 = 2、ways(3) = 2+1 = 3、ways(4) = 3+2 = 5 ……

ねこ博士
大きな問題の答えを、同じ形の小さな問題の答えで書けた。この式は、プログラムにそのまま書ける。関数 ways が、自分自身を呼ぶんだ。
ways(n) = n が 0 か 1 なら 1、そうでなければ ways(n−1) + ways(n−2)

ねこ博士
関数が自分自身を呼ぶことを再帰と呼ぶ。クイックソートで、左右のグループに同じやり方を使ったのも再帰だった。大事なのは、「n が 0 か 1 なら 1」のように、もう自分を呼ばずに答えが決まる場合(終わりの条件)を必ず書くことだ。これが無いと、関数は永遠に自分を呼び続けて、スタックがあふれてしまう。

うさ美
きれいに書けました。これで10段を計算すると、どうなるんですか?

ねこ博士
ways(5) の呼び出しを、木の形に書いてみよう。ways(5) は ways(4) と ways(3) を呼ぶ。ways(4) は ways(3) と ways(2) を呼ぶ……。

うさ美
ways(3) が、ways(5) から直接1回と、ways(4) の中から1回、2回計算されている。ways(2) はもっと多い……。同じ計算を何度もやり直しています。

ねこ博士
そう。呼び出しの回数を数えると、n が1増えるごとに、だいたい1.6倍ずつ増えていく。n が 40 なら3億回を超える。同じ答えを何度も計算し直しているのが原因だ。

うさ美
一度計算した答えを、どこかに書いておけばいいのでは。

ねこ博士
それが動的計画法(DP)の考え方だ。小さい問題の答えを表に書いておいて使い回す。表を、小さい段から順に埋めていけば、どのマスも、すでに書いてある2つのマスを足すだけで決まる。
素朴な再帰:同じ小問題を何度も計算する。呼び出し回数は n とともに指数的に増える(O(1.6ⁿ) くらい)
動的計画法:小さい順に表を埋め、1マス1回の足し算 → O(n)
メモ化:再帰の形のまま、一度計算した答えを表に書いて、次からはそれを返す。同じく O(n)

うさ美
書き方は同じ再帰でも、表があるかないかで、3億回と40回の違いになるんですね。

ねこ博士
そう。動的計画法が使えるのは、2つの条件がそろったときだ。「大きな問題の答えが、小さな問題の答えから作れる」こと、そして「同じ小さな問題が何度も出てくる」こと。カーナビの経路、文章の似ている度合い、限られた予算での最善の買い物など、多くの問題がこの形をしている。STAGE7 のダイクストラ法も、「確定した町の最短距離」を表に書いて使い回していたね。
確認クイズ
Q1. 階段の上り方 ways(n) = ways(n−1) + ways(n−2) が成り立つ理由は?
正解! 最後の一歩で場合分けすると、重なりも漏れもなく2つに分かれる。それぞれの数を足せばよい。
Q2. 素朴な再帰で ways(40) を計算すると、とても遅い理由は?
正解! 呼び出しが木の形に広がり、同じ値を何度も計算し直す。回数は n とともに指数的に増える。
Q3. 再帰の関数に必ず書かなければいけないのは?
正解! 終わりの条件が無いと、自分を呼び続けてスタックがあふれる。表(メモ化)は速くするための工夫。