こんにちは！ganariyaです。
最近ほとんど遊んでないので、遊びたいですが遊ぶ相手がいません･･･(かなしい)
さて！(切り替え！)
プログラミング始めたてあるあるなのですが、再帰関数、みなさんどのような印象でしょうか･･･
再帰関数は、プログラミングを始めた頃の最初の関門であり、なかなかイメージし辛く、書きづらい、何をしているのかがよく分からない内容です。
しかし、再帰関数は最初理解するのが難しいですが、一度理解してしまえば応用しやすい概念・テクニックであり、色々なことに応用できます。
今日は、その再帰関数の考え方やどのようなお気持ちで書くのかについて、(出来るだけ)分かりやすく書いてみようと思います。
- そもそも再帰関数とは？
- 再帰関数はどういうところで活用されてる？
- 再帰関数の考え方
- 具体例を見ていこう！①
- 具体例を見ていこう！②
- 再帰関数を書く時に意識すべきこと
- まとめ
- 運営会社 / サービス
- PS
そもそも再帰関数とは？
再帰関数とはなんなのでしょうか？
アルゴリズムの授業などで教授が言っているのはおそらく
辺りだと思います。
これらの共通点は
- すべての状態で、同じ似たような処理が行なわれる。
という点です。
例えば階乗ならのように、似たような処理が行なわれています。
また、フィボナッチ数列ものように繰り返し同じ処理を再帰的に行ないます。
高校でやった漸化式も再帰的ですね。
このような似た処理を何度も行えるものを、「問題を小さくして、ボトムアップに答えを求める分割統治法」といい、再帰は基本的に「同じ問題を再帰で小さく細かく分割して、その小さい問題も元の大きい問題と同じ処理が適用されるので、それなら一個の関数で全部やっちゃえ」っていう考え方です。
ここらへんはまだ難しいと思うので、いまのところは再帰は「同じ似たような処理を繰り返し何度もやるんだな〜〜」って思ってください。
再帰関数はどういうところで活用されてる？
再帰関数はどういったところで活用されているんでしょうか。
実は色々なところで基本的アイディアとして使われています。
迷路探索
例えば、迷路を探索するときは再帰関数、俗にいうDFS(Depth First Search)を使うことが多いです。
始点SからゴールGを目指していく時
再帰関数その頂点の周囲4マスにゴールに繋がる道があるか？
を再帰的に呼び出して、ゴールまで道があるかを、どんどん深くまで探していきます。
もしゴールについたら、呼び出し元についたよ〜っていうのを知らせます。
おそらく、このついたよ〜〜っていうのを呼び出し元に返すっていうのはまた、イメージし辛いと思います。
これは再帰関数の考え方という項目で説明していきます。
パズルゲーム
某人気パズルゲームで、4つ以上玉が集まると玉が一気に消えて、連鎖を狙うぷよっとしたゲームがあります。(伝わる･･･？)
このパズルゲームも再帰関数に似たことを行っています。
再帰関数各ぷよの周囲4マスに似た色がある？
を再帰的に呼び出して、どのぷよが消えるかを判定しています。
他にも色々ある！
他にも色々な場所で再帰関数は使用されています！
再帰関数を使えば
- 同じ処理を書かなくて良い
- 入力サイズに影響されない(これは後で説明していきます。)
などのメリットがありますね！
ではそのような再帰関数はどのように考えたらいいのでしょうか。
再帰関数の考え方
ここからが再帰関数を理解する上で大切な点です。
しっかり考えていきましょう。
再帰関数を理解するには「会社・社員の上下関係は再帰関数だ！」を理解すると早いと思っています。
会社・社員の上下関係
実は、会社・社員の上下関係は再帰関数だったのです！！！！
(ここで、みんな驚愕して息を呑む。)
･･･と、言っても、「そんなことないやろ〜〜〜」ってなるので、実証パートに移ろうと思います。
会社、社員の上下関係で再帰関数を理解するために、以下の例で考えてみようと思います。
とあるソフトウェアA会社のお話
とあるソフトウェア会社であるA社では、多くの社員、部長などがいる大企業であり、お歳を召した社長や取締役などのお偉いさんが会議をしていました。
「近頃は、機械学習っつうもんが流行っているらしいの〜〜〜〜」
「なにやら、いろんなあらゆることを勝手に便利にやってくれるんじゃての･･･」
「ありゃ〜〜〜そりゃ便利じゃの。」
「よくわからんが我が社でもやってみることにするのじゃ！」
会社内は阿鼻叫喚です。
それもそのはず、突然あらゆるソフトウェア開発に機械学習を取り入れるという話が、お偉いさんたちから上がってきたのです！
その後、代表取締役から社長に次のようなメッセージが届きました。
「機械学習を我が社で導入するために、必要な最小コストを調べといてくれ。」
社長はびっくりし、自分で調べるのは面倒だなってなりました。
そこで、社長の部下である部長たちに
「代表取締役から、機械学習を我が社で導入したいという声が出た。そのため、お前ら、わしの代わりに、必要な最小コストを調べといてくれ。」
と、部下である部長たちに全てやらせ、その後部下から報告された調査書の中で一番小さいコストのものを採用し、自分でまるでやったかのように、代表取締役に報告するようです。
部長たちも困りました。
そこで、部長たちも同様に、自分の部下である次長に
「機械学習を我が社で導入するために、必要な最小コストを調べとけ！」
とやらせました。
次長たちも負けじと自分の部下である新人に
「必要な最小コス(ry」
と伝えました。
ここで、困ったのが新人たちです。
彼等には部下が居なかったのです！(新人なので当たり前か)
新人たちは、しぶしぶ機械学習に導入に必要なコストを調べ、その調査書を彼らそれぞれの上司である次長に渡しました。
次長は、新人から貰った中で一番小さいコストの調査書を採用し、自分でやったかのように、部長に渡しました。
その後の、部長->社長->代表取締役も同様です。
そして、最後に代表取締役は
「機械学習のコストを調べました！」
と、今この記事を読んでいるあなた(あなたです)に渡しました！
不毛な機械学習コストを調べさせた真犯人はあなただったのです！(なんだってー！？)
イラストで会社Aの例を解説する
上記の会社Aの例は、再帰関数がやっていることそのものです。
どうして再帰関数なのかを説明していこうと思います。
まず、代表取締役は、自分の部下である社長たちに一番小さい機械学習のコストを調べさせました。
同様に、社長たちも自分の部下である部長たちにコストを調べさせました。
そして、最後に部長たちも自分の部下である、部下たちにコストを調べさせました。
例中だと次長が出てきていますが、カットしています。
すると、部下たちは困りました。
自分に部下が居ないのです。
仕方ないので、彼等は最小コストを各自求めました。
そして、彼等は各自求めたコストの調査書を各自の上司(部長)に渡しました。
すると、部長たちは、まるで自分が計算したかのように、新人たちの中で一番小さいコストを自分の上司(社長)に渡したのです！
社長たちも同様に、まるで自分が計算したかのように、部長たちの中で、一番小さいコストを自分の上司である代表取締役に渡しました。
そして、最後に代表取締役が、社長たちから受け取った一番小さいコストをまるで自分で計算したかのように、あなたに答えを渡したのです。
再帰関数の考え方
再帰関数の定義
イラストでなんとなく、再帰関数の感覚を掴んでもらえたでしょうか。
上記の再帰関数 は
自分を含む自分の権力以下で調べることのできる最小コストを求める。
となります。(自分を含むというところもポイントです。)
例えば、（社長取締役）は、社長取締役自分自身を含む、自分の権力以下(社長取締役自身、部長、新人)で調べることのできる最小コストを求める。となります。
また、（部長）は、部長自分自身を含む、自分の権力以下(部長自身、新人)で調べることのできる最小コストを求める。
となります。
このように、再帰関数は自分を含んだ自分以降の関数であり、再帰的に部下に仕事をやらせます。
再帰関数自身で出来ること
再帰関数自身は何が出来るのでしょうか。
例えば、（社長）について考えてみます。
社長自身は何か自分自身で調べるのでしょうか？
･･･社長自身は何も調べません。
自分で調べることが出来ないので、全て部下にやらせます。
そして、受け取った値を色々といじくって、まるで自分でやったかのように、自分の成果として上司に渡すのです。
再帰関数自身が行なうこと
結局再帰自身が行なうことは
- 自分で計算ができないので、部下に代わりにやらせる
- 部下が計算したものを、まとめ上げて、自分がやったかのように上司に返す！
です。
そして、自分で計算ができないので、部下に代わりにやらせるが再帰関数のキモで、呼び出された部下も、自分自身で計算ができません。
よって、呼び出された部下も、その部下を呼び出し、代わりに仕事をやらせます。
これが何度も似たような処理を呼び出しているように見えて、再帰関数と言われるのです！
再帰関数自身が行なう作業の範囲
よって、実は再帰関数が定義する内容は非常に少ないです。
以下の三つのみです。
- 上司から状態、条件が与えられて呼び出される。
- 呼び出されたものの、自分で計算はできないので、部下に状態、条件を与えながら部下を呼び出して代わりに計算させる。
- 部下から貰った結果たちを処理して、自分がやったかのように結果を上司に返す。
シンプルですね。
つまり、図でいうと
青丸が再帰関数自身です。
この再帰関数は上司から呼び出され、状態や条件を与えられて、仕事を任されました。
しかし、自分では出来ないので、部下に状態や条件を与えながら仕事を任せました。これは青丸から右側にでている矢印に当たります。
そして、矢印先の部下である再帰関数から受け取った結果を貰って、その結果を青丸でいろいろと弄ってから、上司側に結果を返します。結果を返すのは、図では青丸から左側に出ている矢印に当たります。
なのでコーディングするときは、
- この関数は上司からどういう条件が与えられるのかな〜
- この関数は部下にどのような状態・条件を与えて処理を変わりにやらせるのかな〜
- 部下から受け取った結果たちを、青丸（再帰関数）自身でどのように処理しようかな〜
- 上司に何を返そうかな〜〜
を意識すると非常に書きやすいです。
ちなみに、急に条件・状態というワードが出てきて戸惑っていると思います。
実は再帰関数は、上司から条件や状態が与えられ、その条件下で部下に仕事をやらせます。
また、部下に仕事を代わりにやらせるときも、条件や状態を与えて仕事をやらせます。状態や条件を与えると、どのような仕事をするか分からず暴発するかもしれません！
図だと、この条件や状態は青丸から出る右向きの矢印に当たり、矢印先に仕事をやらせるときに条件、状態を部下に与えるのです。
意外と再帰関数自身がやることは少ないのですね！
再帰関数自身がやることは
- 部下に命令を渡すために矢印(条件・状態)を与えながら、部下に仕事をやらせる。(つまり、再帰関数、青丸から出る右側方向の矢印は再帰関数自身が扱う内容。)
- 部下が計算した結果を受け取って、青丸自身で処理して、それを上司に自分がやったかのように返す。(処理をするのは青丸・再帰関数自身で、結果を返すのは左側方向にでる矢印。)
この、条件や状態については、後のプログラム上での具体例で見ていきましょう！
最後に新人・プログラムの終了について
実は大切なことを忘れていました。
このプログラムはいつ終了するのでしょうか？
今、私達の再帰関数の認識では
自分では計算できないから部下に、条件や状態を与えて仕事を任せる。
です。
しかし、このままでは部下がその部下を呼び、その部下の部下が部下の部下の部下を呼び、その.....
と永遠に終わりません。
しかし、大丈夫です。
一番下っ端である新人が必ず存在し、その新人は部下がおらず、仕事を部下に代わりにやらせることが出来ません。部下がいないからです。
よって、新人は、新人自身で処理をさせます。ついにここで負の連鎖が途切れるのです。(かわいそう)
よって、再帰関数には必ず場合分けが存在します。
部下が居なければ強制的にその場で値を自分自身で(新人自身で)求めて、上司に返すのです。
この、「部下が居なければ、強制的にその場で自分自身で求めて、上司に返す」という場合分けは、プログラム例で見ていきましょう！
具体例を見ていこう！①
まずは再帰関数の代表例である階乗の計算を見ていきます。
自然数の階乗は
と表され
となります。
これを再帰関数を定義してプログラムを書いてみます。
まず、以下に再帰を計算するプログラムを書いてみます。
//f(x) //**xを含む** //x以降の階乗を計算して返す int f(int x) { //新人の場合分け if (x == 1) { return 1; } //f(x-1)は自分で計算できないので部下にやらせる int buka = f(x-1); //xは自分が担当する int ret = x * buka; //結果を上司に返す return ret; } int main() { int n; cin >> n; cout << f(n) << endl; return 0; }
再帰関数の定義
再帰関数を書く時に意識すること１つ目として
「その再帰関数が何を求めるのか。」
です。
今回求めたいのは、階乗の結果なので、当然再帰関数は階乗の結果を返します。
では、再帰関数はどのような値の階乗を返すのでしょうか。
ここで、大事な考え方として
「再帰関数は自分自身を含む、自分以降の計算を、部下を利用しながら行なう。」
という点です。
なら、自分自身を含む自分以降、つまり5~1までの階乗の計算を行ないます。
また、なら、自分自身を含む自分以降、つまり10~1までの階乗の計算を行ないます。
この自分自身を含む自分以降は大切な考え方です。
これで再帰関数のやらないと行けない計算がわかりました。
上司から条件が与えられる
再帰関数ですが、階乗を求めるためには先程述べたように、どのような数以降の計算をするのか？という情報がないといけません。
例えば、なら、自分自身を含むので、10~1までの階乗を計算すればいいのか！となりますが、10という情報が無ければ、どんな数の階乗の計算をすればいいんだ？となってしまいます。
ここで、再帰関数は上司から呼び出されるということを思い出してもらえればと思います。
//引数のxは上司から与えられる！！！！！ int f(int x) { //新人の場合分け if (x == 1) { return 1; } //f(x-1)は自分で計算できないので部下にやらせる int buka = f(x-1); //xは自分が担当する int ret = x * buka; //結果を上司に返す return ret; } int main() { //あなたが呼び出す //つまり、あなたが一番上司、再帰関数の犯人 cout << f(13) << endl; return 0; }
再帰関数は引数
をもらっています。
つまり、再帰関数に与えられる引数が、上司から与えられる条件・状態なのです！！
ピンと来ていないと思うので、きちんと説明します。
まず、あなたが一番の上司です。
上のプログラム例では、main文のなかでとあなたが呼び出しており、これは
「13!の階乗を計算しといて！！！！」
とあなたがプログラムに仕事をやらせているのです。
呼び出された再帰関数くんは戸惑いました。
「どんな階乗を返せばいいんだろう･･･」
ここで再帰関数くんは引数を見てみました。
と入っていたのです。
再帰関数くんは安心です。自分自身を含む、つまり13以降の階乗を自分が求めればよいとわかったからです。
以上のように、再帰関数は引数で条件や状態が上司から与えられ、その条件、状態下で自分を含む以降の計算をします。
自分ができることは自分でやり、できないことは部下にやらせる。
上記の引数が与えられた再帰関数
くんにもういちど注目して説明します。
再帰関数くんは13以降の階乗の計算を行なわないといけません。
しかし、困りました。
くんは、13が分かっているため、
のうち、
は自分自身で行なうことが出来ます。
しかし、12以降の階乗の計算は自分ではわかりません。
よって、部下であるに変わりにやらせることにしました。
このように再帰関数には自分自身で出来ることと、出来ないことがあります。 自分で出来ないことは
//f(x-1)は自分で計算できないので部下にやらせる
int buka = f(x-1);
部下にという条件、状態を与えて仕事を変わりにやらせて、その結果を貰います。
そして、部下から貰った値をいじくります。
今回の例では、自分自身で計算できるをかけるという行為をやっています。
//xは自分が担当する
//これで階乗が計算できた
int ret = x * buka;
こうして自分自身を含む、自分以降の計算が計算できました。
そして、最後に再帰関数くんは、まるで自分が全部計算したかのように、呼び出し元・上司へとその答えを返すのです。
//結果を上司に返す
return ret;
このように再帰関数は
- 上司から条件と状態が与えられる。
- 再帰関数は、自分自身を含む自分以降の計算をしないといけない。
- しかし、自分で計算できない部分があるため、そういうのは部下に条件・状態を与えて代わりに計算させる。（図では、右方向側にでる矢印に当たる）
- 部下が計算した結果たちを自分でいじくり、自分ができることを行なう。(仕上げ)
- そうして出来た結果を、上司に、まるで自分が全部やったかのように返す。
という流れを、再帰的に行っています。
意外と要素ごとに分割するとシンプルなのですね。
終了条件・新人を忘れないようにしよう！
上記の再帰関数は、自分でできないことを部下にどんどんやらせていました。
そうするとこの再帰関数は永遠と仕事を部下に任せて、永遠に終了しません。
そこで、きちんと終了条件を場合分けで明記する必要があります。
//新人の場合分け
if (x == 1) {
return 1;
}
今回の階乗の計算ではこの部分に当たります。
上司からという条件・状態が与えられ、
以降の階乗の計算をしろ！と命令されました。
しかし、当然ですが1より小さい値の階乗は、当然1です。
よって、これ以上仕事を部下にやらせることが出来ません。
ゆえに、もしだったら、その時点で、この新人の再帰関数は強制的に値を返すのです。
このように確実に終了条件を書くようにしましょう。
具体例を見ていこう！②
次の例として、もう少し複雑なものを見ていきます。
以下のような例です。
問題例
この会社には人の人がいる。それぞれの人には
~
の番号が付けられている。
番の人が一番偉い社長である。
この会社には個の上下関係があり、
番目の上下関係では、
は
の上司である。
この会社の給料は以下のように決められている。
新人、つまり部下が一人も居ない人は強制的に1万円である。
それ以外の人たちは、直属の部下の給料の合計の2倍が、自分の給料となる。
このときの社長の給料を答えよ。
ソースコード
#define MAX_N 10010 vector<int> G[MAX_N]; //頂点vの人のお給料を返す int f(int v) { //部下がいないなら //強制的に1を返す if (G[v].size() == 0) { return 1; } int ret = 0; for (int i = 0; i < G[v].size(); i++) { //部下 int to = G[v][i]; //部下の給料を求めさせて //その給料を足す ret += f(to); } //自分は部下の給料の2倍 ret *= 2; return ret; } int main() { int N; cin >> N; for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); } int ret = f(0); cout << ret << endl; return 0; }
再帰関数fの定義
さて、再帰関数はどのように定義するべきでしょうか。
前回同様意識することは
自分自身を含めて、計算を行なう。
ということです。
よって、今回の再帰関数は、自分自身の頂点のお給料を求める。となります。
上司から条件が与えられる
今回でも上司から引数で条件・状態が与えられます。
は頂点10(番号10)の人のお給料を求めろ！となります。
自分ができることは自分でやり、できないことは部下にやらせる。
さて、再帰関数fの求めたい値は、番号の人のお給料です。
しかし、頂点の人のお給料を求めるには、直属の部下のお給料の合計がわからないといけません。
よって、部下に仕事を任せます。
int ret = 0; for (int i = 0; i < G[v].size(); i++) { //部下 int to = G[v][i]; //部下の給料を求めさせて //その給料を足す ret += f(to); }
お前の番号はだ(条件・状態を与える)！お前のお給料を求めてこおい！！
という感じです。
このように自分で求められないものは部下にやらせます。
そして、その後、自分自身で計算できる部分である二倍を行ない、上司に自分のお給料を自分で求めました〜〜〜〜って返します。
//自分は部下の給料の2倍
ret *= 2;
return ret;
基本的なところは階乗と代わっていませんね。
終了条件・新人を忘れないようにしよう！
しかし、このままだと永遠に部下のお給料を訪ねていると、計算が終わりません。
ただ、絶対にこの会社の一番下っ端の新人は一人も部下がおらず、そのような人間のお給料は1万円と分かっています。 よって、以下のように場合分けをします。
//部下がいないなら //強制的に1を返す if (G[v].size() == 0) { return 1; }
このように必ず終了条件を書きましょう！
この例と階乗の一番の違い
この例と、階乗の例、二つを見てきました。
どこか、決定的に違う部分があったのですが、何かわかったでしょうか。
それはfor文の存在です。
今回の例では、forが存在しましたが、階乗の例ではfor文が存在しませんでした。
実は通常、再帰で書くべきものはfor文が出てくることが多いです。
直属部下が一人しかいない階乗は、実は以下のように計算することが出来ます。
int main() { int N; cin >> N; int ans = 1; for (int i = N; i >= 1; i--) ans *= i; cout << ans << endl; return 0; }
なぜならば、階乗は部下が一人しか居ないため、再帰せずとも書けてしまうからです！
しかし、この例(社員のお給料)では違います。 部下の数がそれぞれ異なるからです。
このように、直属の部下の数が異なる場合は、main文内のforでは単純に求めることが出来ません。
部下の数が分かっていないからです。
しかし、再帰を使えば、各頂点・状態ごとの部下の数がそれぞれの再帰関数内で分かるため、それぞれの再帰関数のforで、部下の数だけ仕事を代わりにやらせることが出来るのです！！
再帰は便利ですね！
再帰関数を書く時に意識すべきこと
さて、再帰関数を見てきました。
ここまで見れば、ある程度再帰について理解が進んだのではないでしょうか。
再帰で意識するべきことを振り返りましょう。
何をするべき再帰関数かはっきりさせる
その再帰関数で、何を求めたいのでしょうか。
階乗の例ではは、自分自身を含む
以降の階乗を求めるということでした。
自分自身を含むということを意識しながら、何を求めたいのかをはっきりさせましょう。
上司(呼び出し元)から条件・状態が与えられる。
再帰関数では、引数でその再帰関数の条件、状態が与えられ、その条件・状態下で答えを計算します。
階乗の例では、は、10以降の階乗を求めてね！という条件が与えられていますね。
自分で求められないものは、部下に条件を与えながら仕事を代わりにやらせる
再帰関数は、自分で計算できない部分が絶対にあります。
そういうものは、部下の再帰関数の引数に、条件、状態を与えて代わりに計算させましょう。
自分でできないものは部下にやらせればいいのです！かしこい！
部下から貰った値を弄って、自分でやったかのように上司に返す
部下に仕事を代わりにやらせると、部下たちから結果がそれぞれ返ってきます。
それらの値を弄りながら、自分の仕事を行ないます。
最低限何か再帰関数は自分自身でやるはずです。(for文で仕事をやらせるだけも、立派な仕事です･･･？)
その結果をまとめて、色々といじって、「私が計算しました。」と上司に返します。
ずるいですね･･･
終了条件をきちんと書く
再帰関数は、永遠に部下に任せ続け、そのままだと終わりません。
なので、きちんと場合分けで終了条件を書きましょう。
なんか、再帰が終わらないな〜ってときは、おそらく終了条件を書き忘れてます。
困ったら図を書こう
なかなか再帰関数は最初のうちは、書けません。
そういうときは、図を書いて、矢印がどちら方向に出ているのか
右方向なら、仕事を任せ、条件状態を部下に与えて仕事をやらせています。
そして、その後部下から結果を貰い、その値をまとめて弄って、左側の上司に返します。
というのを、はっきりさせるといいと思います。
まとめ
再帰関数についてまとめてみました。
なかなか難しいところもあったかもしれません。
しかし、再帰関数は、TechFULの問題はもちろん、実社会で多く使用されています。
是非、マスターしてアプリ制作などで使用してみてください！
ガナリヤでした！
運営会社 / サービス
444株式会社
TechFUL
PS
再帰関数の中では
void f(親から与えられるこの再帰関数の条件・状態){
}
という返り値がないものがあります。
これは、部下に条件、状態を与えて計算させることが目的であり、値をその後で貰うということが必要ないパターンです。