Time Limit: 0 msec / Memory Limit: 0 KB
キーポイント
- 「ある関数の中で同じ関数を呼び出す」ことを再帰呼び出しという
- 再帰を行うような関数を再帰関数という
- 再帰呼び出しを行わずに完了できる処理をベースケースという
- 再帰呼出しを行い、その結果を用いて行う処理のことを再帰ステップという
- 再帰関数の実装方法3ステップ
- 1.「引数」「返り値」「処理内容」を決める
- 2.再帰ステップの実装
- 3.ベースケースの実装
再帰関数
再帰関数を理解するためには関数を理解している必要があります。 1.15.関数の記憶が曖昧な人は復習しておきましょう。
再帰関数は難しいので、説明を読んでみて分からなかった場合はそのまま次に進んでもかまいません。
繰り返し処理を行う方法として、これまでforループやwhileループのようなループ構文を扱ってきました。
再帰も繰り返し処理を行う方法の一つです。
再帰とは「ある関数の中で同じ関数を呼び出す」ことです。また、このような関数のことを再帰関数といいます。
再帰はループ構文よりも強力な繰り返し手法で、ループ構文で書くのが難しいような処理を簡潔に行うことができます。
初めは分かりにくく感じるかもしれませんが、強力な手法なので使いこなせるようにしましょう。
例として、「0からnまでの総和を計算する関数」を考えます。
これは今まで扱ってきたforループやwhileループを用いて書くことができますが、再帰関数を用いて書くと次のようになります。
#include <bits/stdc++.h> using namespace std; int sum(int n) { if (n == 0) { return 0; } // sum関数の中でsum関数を呼び出している int s = sum(n - 1); return s + n; } int main() { cout << sum(2) << endl; // 0 + 1 + 2 = 3 cout << sum(3) << endl; // 0 + 1 + 2 + 3 = 6 cout << sum(10) << endl; // 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55 }
実行結果
3 6 55
sum関数の中でsum関数を呼び出しています。このような関数呼び出しのことを再帰呼び出しと言います。
再帰関数の動作
次のスライドは上のsum関数をsum(3)
として呼び出したときの動作を説明したものです。
再帰関数は関数名が同じなので自分自身を呼び出しているように感じられて動作が分かりにくく思えるかもしれません。
その場合は「引数の異なる呼び出しでは別の関数を呼んでいる」と考えるといいです。
上の例でsum(3)
を呼び出したときの動作を書き出してみます。
sum(3)
ではsum(2)
を呼び出してその結果に3を足して返します。sum(2)
ではsum(1)
を呼び出してその結果に2を足して返します。sum(1)
ではsum(0)
を呼び出してその結果に1を足して返します。sum(0)
は0を返します。
ここで、呼び出されるsum(3), sum(2), sum(1), sum(0)
をそれぞれ別々の関数に切り出して考えてみると次のようになります。
#include <bits/stdc++.h> using namespace std; // 0~0の総和を求める int sum0() { return 0; } // 0~1の総和を求める int sum1() { int s = sum0(); return s + 1; // (0~0の総和) + 1 = 1 } // 0~2の総和を求める int sum2() { int s = sum1(); return s + 2; // (0~1の総和) + 2 = 3 } // 0~3の総和を求める int sum3() { int s = sum2(); return s + 3; // (0~2の総和) + 3 = 6 } int main() { cout << sum3() << endl; // 6 }
実行結果
6
sum1, sum2, sum3
は同じような処理をしていますが、sum0
だけは異なる処理をしています。
繰り返しの処理をwhile文やfor文を用いてまとめられたように、
このような繰り返しの呼び出しを再帰呼出しでまとめることができます。
もう一度元の再帰関数を見てみましょう。
#include <bits/stdc++.h> using namespace std; // 0 ~ nの総和を求める int sum(int n) { if (n == 0) { // sum0のケースを場合分け return 0; } // それ以外のケース int s = sum(n - 1); // 1~(n-1)の総和を計算 return s + n; // nを足して返す } int main() { cout << sum(3) << endl; // 6 }
実行結果
6
再帰関数が正しく動作するのは再帰呼び出しの連鎖に終わりがあるからです。
この例ではn
が初めに呼び出されたときの値から1ずつ減っていき、0になるとif文によって分岐され、それ以上再帰呼出しが起こらなくなり、
呼び出しの連鎖が終わるのでうまく動きます。
再帰関数の性質
実装法を紹介する前に再帰関数の性質をまとめておきます。
再帰関数の内容は大きく分けると以下の2つの処理に分類できます。
- ベースケース:再帰呼び出しを行わずに完了できる処理
- 再帰ステップ:再帰呼出しを行い、その結果を用いて行う処理
sum関数の例では、ベースケース・再帰ステップはそれぞれ次のようになります。
// n を受け取って、0~n の総和を計算して返す関数 int sum(int n) { // ベースケース if (n == 0) { return 0; } // 再帰ステップ int s = sum(n - 1); return s + n; }
また、再帰関数が正しく動作するためには次の条件を満たす必要があります。
- 再帰呼び出しの連鎖に終わりがある
これを言い換えると、「再帰ステップでの再帰呼び出しを繰り返すうちに必ずベースケースに到達する」ということになります。
この条件を満たさない場合、無限ループになってしまいます。
再帰関数の実装法
初めのうちは、そもそも再帰関数でどのような処理を行うことができるのかが分からず、 使いこなすのが難しいかもしれませんが、再帰関数の実装を追いかけたり、実際に実行してみるうちに分かってくるはずです。
ここでは、再帰関数の実装の方法をできるだけ丁寧に説明します。
1.「引数」「返り値」「処理内容」を決める
関数では、処理に必要な変数を引数として受け取り、関数の内部で処理を行い、結果を返すという流れで処理を行うので、 「引数」「返り値」「処理内容」を決める必要があります。
「処理内容」は「返り値」を計算するという内容になり、結局同じことを示すことも多いです。
sum関数での例
引数 | int n (0以上の整数) |
返り値 | 0 \sim nの総和 |
処理内容 | 0 \sim nの総和を計算する |
ここで関数の概形が決まります。sum関数の例を次に示します。
// 0 ~ n の総和を返す int sum(int n) { // 処理内容 : 0 ~ n の総和を計算する }
2. 再帰ステップの実装
次に、「具体的にどのような再帰呼び出しを使って処理を実現できるのか」つまり、再帰ステップの内容を考えます。
「処理内容」を実装するために、「引数を変えて再帰呼び出しした結果」を利用できないかを考えましょう。 ここは実装したい処理によって異なるので慣れるまで難しいかもしれません。
sum関数での例
「0 \sim nの総和」は「0 \sim (n-1)の総和」にnを足すことで計算できます。
ここで「0 \sim (n-1)の総和」はsum(n - 1)
という再帰呼出しによって得られます。
// 0 ~ n の総和を返す int sum(int n) { // 処理内容 : 0 ~ n の総和を計算する // 再帰ステップ int s = sum(n - 1); // 0 ~ (n-1) の総和 return s + n; // 0 ~ n の総和 }
3. ベースケースの実装 (再帰呼び出しを行わずに完了できる処理)
まず、どのような場合がベースケースなのか、つまり「再帰呼び出しを行わずに完了できる」かを考えます。
次に、ベースケースをif文で場合分けして、処理を実装します。
適当な引数を与えたときに、再帰ステップでの再帰呼び出しが最終的にベースケースに到達することを確認しておきましょう。今考えたベースケースに到達しない場合は再帰ステップもしくはベースケースが間違っています。もう一度考え直してみましょう。
ベースケースは複数あることもあるという点に注意してください。
sum関数での例
sum関数は「0 \sim nの総和」を計算する関数なので、n == 0
の場合はすぐに結果が0だと分かります。従ってこのケースがベースケースに相当します。
また、2で実装した再帰ステップでの再帰呼出しsum(n - 1)
は、最終的にn == 0
のケースに到達するので、必ずベースケースに到達することが分かります。
// n を受け取って、0~n の総和を計算して返す関数 int sum(int n) { // 処理内容 : 0 ~ n の総和を計算する // ベースケース if (n == 0) { return 0; // 再帰呼び出しをせずとも 0 という結果が確定している } // 再帰ステップ int s = sum(n - 1); // 0 ~ (n-1) の総和 return s + n; // 0 ~ n の総和 }
これで再帰関数sum
は完成です。
もう一度再帰関数の書き方まとめます。
- 「引数」「返り値」「処理内容」を決める
- 再帰ステップの実装
- ベースケースの実装
はじめのうちは再帰関数の実装は難しく感じると思います。 しかし、何度も再帰関数を読んだり書いたりしているうちに、直感的に納得できるときが来るはずです。
なお、再帰ステップを考えてからベースケースを考える流れで説明しましたが、 必ずしも先に再帰ステップを考えるのがよいとは限りません。 場合によってはベースケースを先に考えた方が考えやすかったり、再帰ステップで使う関係式を考えているうちにベースケースを思いつくこともあるかもしれません。 「再帰呼び出しの連鎖に終わりがある」という条件さえ満していれば大丈夫ですので、自由な発想で書いてみてください。
再帰関数の実装例
再帰関数のいくつかのパターンを紹介します。 for文やwhile文を用いた方が簡潔に書けるようなものもありますが、再帰関数の例として挙げています。
AからBまでの総和を求める関数: sum_range
クリックで開く
2つの整数aとb (a \leq b) について、a, a+1, \ldots, b - 1, bの総和を計算する関数`sum_range`を再帰関数で実装します。 具体的な例を挙げると、`sum_range(3, 7)`なら、3+4+5+6+7=25なので、25を返します。 #### 1. 「引数」「返り値」「処理内容」を決める ||| |---|---| |引数|`int a`, `int b`| |返り値|a \sim bの総和 (`int`型)| |処理内容|a \sim bの総和を計算する|// a ~ bの総和を計算する (a ≦ b)という前提 int sum_range(int a, int b) { }#### 2. 再帰ステップの実装 「a \sim bの総和」=「a \sim (b - 1)の総和」+ bという関係式が成り立ちます。 「a \sim (b - 1)の総和」の部分は、引数`b`を1減らして`sum_range`を再帰呼出しした結果に対応するので、この関係式を実装したものが再帰ステップとなります。
// a ~ bの総和を計算する (a ≦ b)という前提 int sum_range(int a, int b) { // 再帰ステップ return sum_range(a, b - 1) + b; //「a~bの総和」=「a~(b-1)の総和」+ b }#### 3. ベースケースの実装 再帰呼出しせずに結果が確定するようなケースを考えます。 `a == b`のとき「a \sim bの総和」=「a \sim aの総和」=「a」となるので、このケースがベースケースになります。 また、2で実装した再帰ステップでは、aは変化せずbは1ずつ減って再帰呼び出しの連鎖が起こります。a \leq bという関係より、bは最終的にaと等しくなるので、再帰呼出しに終わりがあることが分かります。
// a ~ bの総和を計算する (a ≦ b)という前提 int sum_range(int a, int b) { // ベースケース if (a == b) { return a; } // 再帰ステップ return sum_range(a, b - 1) + b; //「a~bの総和」=「a~(b-1)の総和」+ b }--- これで`sum_range`は完成です。
#include <bits/stdc++.h> using namespace std; // a ~ bの総和を計算する (a ≦ b)という前提 int sum_range(int a, int b) { // ベースケース if (a == b) { return a; } // 再帰ステップ return sum_range(a, b - 1) + b; //「a~bの総和」=「a~(b-1)の総和」+ b } int main() { cout << sum_range(0, 4) << endl; // 0 + 1 + 2 + 3 + 4 = 10 cout << sum_range(5, 8) << endl; // 5 + 6 + 7 + 8 = 26 }##### 実行結果
10 26この実装例では「a \sim bの総和」=「a \sim (b - 1)の総和」+ bという関係式に着目して、`sum_range(a, b - 1) + b`と`b`を減らしていく方針で実装しましたが、 「a \sim bの総和」=「(a + 1) \sim bの総和」+ aという関係式も成り立つので、`sum_range(a + 1, b) + a`と`a`を増やしていく方針で実装することもできます。
// a ~ bの総和を計算する (a ≦ b)という前提 int sum_range(int a, int b) { // ベースケース if (a == b) { return a; } // 再帰ステップ return a + sum_range(a + 1, b); //「a~bの総和」= a +「(a+1)~bの総和」 }
配列の要素の総和: array_sum
クリックで開く
引数(参照)で与えられた`int`型の配列の全ての要素の総和を計算する関数`array_sum`を実装します。 #### 1. 「引数」「返り値」「処理内容」を決める 配列の総和を求める関数なので、引数は配列を参照で受け取ります。 (実はこれではうまく再帰関数として実装できないのですが、ステップ2で確認した後に修正します。) ||| |---|---| |引数| `vector// dataの要素の総和を計算する int array_sum(vector<int> &data) { }#### 2. 再帰ステップの実装 次のような関係が成り立つことが分かります。
「配列の要素の総和」=「配列の先頭の要素」+「配列の2番目以降の要素の総和」しかし、このままではうまく再帰呼出しで計算できません。 この関係式は少し言い換えると次のようになります。
「1番目以降の要素の総和」=「1番目の要素」+「2番目以降の要素の総和」さらに以下のような関係も成り立っています。
「2番目以降の要素の総和」=「2番目の要素」+「3番目以降の要素の総和」 「3番目以降の要素の総和」=「3番目の要素」+「4番目以降の要素の総和」 ...これらは、変数iを使うことで次のようにまとめることができます。
「i番目以降の要素の総和」=「i番目の要素」+「i+1番目以降の要素の総和」「i+1番目以降の要素の総和」の部分は再帰呼び出しで得られます。 ステップ1で決めた引数だけでは不十分で、変数iを引数に追加する必要が出てきました。ステップ1に戻って修正しましょう。 #### 1.「引数」「返り値」「処理内容」を決める (やり直し) 引数に`int i`を追加して「与えられた配列のi番目以降の要素の総和を計算する関数」とすることで、再帰関数として実装できることが分かりました。 この関数の「引数」「返り値」「処理内容」は次のようになります。 ||| |---|---| |引数|`vector
// (補助関数) // dataのi番目以降の要素の総和を計算する int array_sum_from_i(vector<int> &data, int i) { } // dataの全ての要素の総和を計算する int array_sum(vector<int> &data) { return array_sum_from_i(data, 0); }これ以降は`array_sum_from_i`の実装について見ていきます。 #### 2. 再帰ステップの実装 (再) ここまでで、「i番目以降の要素の総和」=「i番目の要素」+「i+1番目以降の要素の総和」の関係式が成り立つことが分かりました。 「i+1番目以降の要素の総和」の部分は`array_sum_from_i(data, i + 1)`と再帰呼出しすることで求めることができます。
// (補助関数) // dataのi番目以降の要素の総和を計算する int array_sum_from_i(vector<int> &data, int i) { // 再帰ステップ int s = array_sum_from_i(data, i + 1); // i+1番目以降の要素の総和 return data.at(i) + s; // 「i番目以降の要素の総和」=「i番目の要素」+ s }#### 3. ベースケースの実装 「i番目以降の要素の総和」なので、対象の要素が無くなったとき、つまり`i == data.size()`のときは答えが0だと分かります。よって、このケースがベースケースとなります。 再帰ステップでは引数の`i`が1ずつ増えて再帰呼び出しの連鎖が起こるので、最終的に`i == data.size()`を満たすはずです。 これより再帰の連鎖に終わりがあることが分かります。
// (補助関数) // dataのi番目以降の要素の総和を計算する int array_sum_from_i(vector<int> &data, int i) { // ベースケース if (i == data.size()) { return 0; // 対象の要素がないので総和は0 } // 再帰ステップ int s = array_sum_from_i(data, i + 1); // i+1番目以降の要素の総和 return data.at(i) + s; // 「i番目以降の要素の総和」=「i番目の要素」+ s }--- これで`array_sum_from_i`は完成です。 `array_sum`を含めたプログラム全体は次のようになります。
#include <bits/stdc++.h> using namespace std; // (補助関数) // dataのi番目以降の要素の総和を計算する int array_sum_from_i(vector<int> &data, int i) { // ベースケース if (i == data.size()) { return 0; // 対象の要素がないので総和は0 } // 再帰ステップ int s = array_sum_from_i(data, i + 1); // i+1番目以降の要素の総和 return data.at(i) + s; // 「i番目以降の要素の総和」=「i番目の要素」+ s } // dataの全ての要素の総和を計算する int array_sum(vector<int> &data) { return array_sum_from_i(data, 0); } int main() { vector<int> a = {0, 3, 9, 1, 5}; cout << array_sum(a) << endl; // 0 + 3 + 9 + 1 + 5 = 18 }##### 実行結果
18
Nが素数であるかを判定する関数 is_prime
クリックで開く
正の整数Nが素数であるかを判定する関数`is_prime`を実装します。 Nだけを引数にとって「Nが素数か」を判定する処理を再帰関数で実装するのは難しいので、`array_sum`と同じように、補助関数を導入します。 「i \sim N - 1の範囲にNの約数が存在するか」を判定する補助関数`has_divisor`を再帰関数として実装します。 Nが3以上のとき、「Nが素数である」という条件は「2 \sim N-1の範囲にNの約数が存在しない」と言い換えることができ、1は素数ではなく、2は素数であるので、 「Nが素数か」を判定する関数`is_prime`は、`has_divisor`を用いて実装できます。 #### 1.「引数」「返り値」「処理内容」を決める ||| |-|-| |引数|`int N` (N \geq 3), `int i`| |返り値| i \sim N - 1の範囲にNの約数が存在するかを`bool`型で返す| |処理内容|i \sim N - 1の範囲にNの約数が存在するかを判定する|// i ~ N-1の範囲にNの約数が存在するか bool has_divisor(int N, int i) { }#### 2. 再帰ステップの実装 / 3. ベースケースの実装 まず、iがNの約数ならば、trueであることが確定します。 そうでないケースでは、「i + 1 \sim N - 1の範囲にNの約数があるか」が結果になります。 「i + 1 \sim N - 1の範囲にNの約数があるか」は再帰呼び出しによって得られます。 iがN以上の場合は、対象となる整数が存在せず、falseであることが確定するので、これはベースケースです。 また、iがNの約数である場合は、trueであることが確定するので、これもベースケースの1つです。 従って、実装は次のようになります。
// i ~ N-1の範囲にNの約数が存在するか bool has_divisor(int N, int i) { // ベースケース1 if (i == N) { // そもそも対象となる整数が無いのでfalse return false; } // ベースケース2 if (N % i == 0) { // 実際にiはNの約数なので、i ~ N-1の範囲に約数が存在する return true; } // 再帰ステップ // i+1 ~ N-1の範囲の結果がi ~ N-1の範囲の結果となる // (ベースケース2によって、iがNの約数の場合は取り除かれているので、あとはi+1 ~ N-1の範囲を調べればよい) return has_divisor(N, i + 1); }--- これで`has_divisor`が実装できました。あとはこれを用いて`is_prime`を実装すれば完成です。
#include <bits/stdc++.h> using namespace std; // i ~ N-1の範囲にNの約数が存在するか bool has_divisor(int N, int i) { // ベースケース1 if (i == N) { return false; } // ベースケース2 if (N % i == 0) { // 実際にiはNの約数なので、i ~ N-1の範囲に約数が存在する return true; } // 再帰ステップ // i+1 ~ N-1の範囲の結果がi ~ N-1の範囲の結果となる // (ベースケース2によって、iがNの約数の場合は取り除かれているので、あとはi+1 ~ N-1の範囲を調べればよい) return has_divisor(N, i + 1); } bool is_prime(int N) { if (N == 1) { // 1は素数ではない return false; } else if (N == 2) { // 2は素数 return true; } else { // 2~(N-1)の範囲に約数が無ければ、Nは素数 return !has_divisor(N, 2); } } int main() { cout << is_prime(1) << endl; // 0 cout << is_prime(2) << endl; // 1 cout << is_prime(12) << endl; // 0 cout << is_prime(13) << endl; // 1 cout << is_prime(57) << endl; // 0 }##### 実行結果
0 1 0 1 0素数判定を行う方法にはもっと効率の良いものがあるので、ここで紹介した素数判定関数は実用的ではないことに注意してください。
配列の操作 reverse_array
クリックで開く
この例は、実装例のみ示します。 各自プログラムの動きを追ってみたり、実際に実行してみたりしてください。 次のプログラムは、参照渡しで与えられた配列を逆順に並べ替えた結果を返す関数`reverse_array`の実装例です。#include <bits/stdc++.h> using namespace std; // dataのi番目以降の要素を逆順にした配列を返す vector<int> reverse_array_from_i(vector<int> &data, int i) { // ベースケース if (i == data.size()) { vector<int> empty_array(0); // 要素数0の配列 return empty_array; } // 再帰ステップ vector<int> tmp = reverse_array_from_i(data, i + 1); // dataのi+1番目以降の要素を逆順にした配列を得る tmp.push_back(data.at(i)); // 末尾にdataのi番目の要素を追加 return tmp; } // 配列を逆順にしたものを返す vector<int> reverse_array(vector<int> &data) { return reverse_array_from_i(data, 0); } int main() { vector<int> a = {1, 2, 3, 4, 5}; vector<int> b = reverse_array(a); for (int i = 0; i < b.size(); i++) { cout << b.at(i) << endl; } }##### 実行結果
5 4 3 2 1
例題 報告書の伝達時間
次の問題はこれまで紹介した例と違い、再帰関数で実装しないと煩雑になるような例です。
難易度が高めなので、少し考えて分からなかったらヒントや解答例を見るようにしてください。
問題文
あなたはA社を経営する社長です。 A社はN個の組織からなり、それぞれに0番からN - 1番の番号が付いています。 0番の番号が付いた組織はトップの組織です。
組織間には親子関係があり、0番以外のN - 1個の組織には必ず1つの親組織があります。 子組織は複数になることがあります。 また、それぞれの組織は直接的または間接的にトップの組織と関係があるものとします。
あなたは全ての組織に報告書を提出するように求めました。
混雑を避けるために、「各組織は子組織の報告書がそろったら、自身の報告書を加えて親組織に送る」ことを繰り返します。
子組織が無いような組織は自身の報告書だけをすぐに親組織に送ります。
ある組織から報告書を送ってから、その親組織が受け取るときにかかる時間を1分とします。
あるタイミングで一斉に報告書の伝達を開始したときに、トップの組織の元に全ての組織の報告書が揃う時刻(伝達を始めてから何分後か)を求めてください。
なお、各組織の報告書は既に準備されているため、報告書の伝達以外の時間はかからないこととします。
制約
- 1 \leq N \leq 50
- 0 \leq p_i < i (1 \leq i \leq N - 1)
入力
N p_1 p_2 \ldots p_{N - 1}
p_iはi番の組織の親組織がp_i番の組織であることを示します。 0番の組織はトップの組織であり、親組織が存在しないことに注意してください。
出力
T
一斉に報告書の伝達を開始したときに、トップの組織の元に全ての組織の報告書が揃う時刻T(開始からT分後)を1行に出力してください。
入力例1
6 0 0 1 1 4
実行結果
3
この入力例では、組織は次のような関係になっています。
- 1番の組織の親組織は0番
- 2番の組織の親組織は0番
- 3番の組織の親組織は1番
- 4番の組織の親組織は1番
- 5番の組織の親組織は4番
この関係は次のような図になります。(子組織から親組織の向きに矢印が向いています。)
次の図は、子組織からの報告書が揃った時刻(集まった報告書を親組織へ送った時刻)を青い文字で、各子組織から受け取った時刻を赤い文字で書き込んだものです。
この図から分かるように、トップの組織の元に全ての組織の報告書が揃う時刻は3となります。
この問題における組織のような構造を木構造といいます。 木構造に関する処理を行う際には再帰関数が有用なことが多いです。
サンプルプログラム
下記のサンプルプログラムを書き換え、次のスライドのような動作をするようにプログラムを完成させてください。
スライドは入力例1のイメージを示したものです。
#include <bits/stdc++.h> using namespace std; // x番の組織について、子組織からの報告書が揃った時刻を返す // childrenは組織の関係を表す2次元配列(参照渡し) int complete_time(vector<vector<int>> &children, int x) { // (ここに追記して再帰関数を実装する) } // これ以降の行は変更しなくてよい int main() { int N; cin >> N; vector<int> p(N); // 各組織の親組織を示す配列 p.at(0) = -1; // 0番組織の親組織は存在しないので-1を入れておく for (int i = 1; i < N; i++) { cin >> p.at(i); } // 組織の関係から2次元配列を作る(理解しなくてもよい) vector<vector<int>> children(N); // ある組織の子組織の番号一覧 // N×0の二次元配列 for (int i = 1; i < N; i++) { int parent = p.at(i); // i番の親組織の番号 children.at(parent).push_back(i); // parentの子組織一覧にi番を追加 } // 0番の組織の元に報告書が揃う時刻を求める cout << complete_time(children, 0) << endl; }
push_back
は配列に要素を追加する操作です。これについては「1.13.配列」で扱っています。
関数complete_time
の引数children
は二次元配列で、
x
番の組織の子組織の番号一覧の配列はchildren.at(x)
とすることで得ることができます。
入力例1の場合のchildren
の中身は以下の表のようになります。
x | children.at(x) |
---|---|
0 | {1, 2} |
1 | {3, 4} |
2 | {} |
3 | {} |
4 | {5} |
5 | {} |
次のようにすることでx
番の組織の子組織についての処理が行えます。
for (int c : children.at(x)) { // (cについての処理) }
ヒント
クリックでヒントを開く
- 「組織xの子組織の報告書が揃う時刻」= 組織xの全ての子組織cについて「組織cからの報告書を受け取った時刻」の最大値 - 「組織cからの報告書を受け取った時刻」=「組織cの元に報告書が揃った時刻」+ 1 - 子組織が無いような組織について、報告書が揃う時刻は0解答例
自分で考えてみたあと、必ず確認してください。
クリックで解答例を開く
#include <bits/stdc++.h> using namespace std; // x番の組織について、子組織からの報告書が揃う時刻を返す // childrenは組織の関係を表す2次元配列(参照渡し) int complete_time(vector<vector<int>> &children, int x) { // ベースケース if (children.at(x).size() == 0) { return 0; // 子組織が無いような組織について、報告書が揃う時刻は0 } // 再帰ステップ int max_receive_time = 0; // 受け取った時刻の最大値 // x番の組織の子組織についてループ for (int c : children.at(x)) { // (子組織 c のもとに揃った時刻 + 1) の時刻に c からの報告書を受け取る int receive_time = complete_time(children, c) + 1; // 受け取った時刻の最大値 = 揃った時刻 なので最大値を求める max_receive_time = max(max_receive_time, receive_time); } return max_receive_time; } // これ以降の行は変更しなくてよい int main() { int N; cin >> N; vector<int> p(N); // 各組織の親組織を示す配列 p.at(0) = -1; // 0番組織の親組織は存在しないので-1を入れておく for (int i = 1; i < N; i++) { cin >> p.at(i); } // 組織の関係から2次元配列を作る vector<vector<int>> children(N); // ある組織の子組織の番号一覧 for (int i = 1; i < N; i++) { int parent = p.at(i); // i番の親組織の番号 children.at(parent).push_back(i); // parentの子組織一覧にi番を追加 } // 0番の組織の元に報告書が揃う時刻を求める cout << complete_time(children, 0) << endl; }##### 入力例1
6 0 0 1 1 4##### 実行結果
3##### 入力例2
8 0 1 2 1 4 3 1##### 実行結果
4##### 入力例3
10 0 0 1 3 2 5 3 4 6##### 実行結果
4
注意点
スタックオーバーフロー
再帰呼び出しは複雑な処理を簡潔に書くことできる便利な機能ですが、 「再帰呼出しの連鎖があまりにも多く続くと実行時エラーが起こる」 という点に注意しなければなりません。
例えば、再帰関数の実装を間違えて、無限に再帰呼出しが起こってしまうようなケースでは実行時エラーが起こります。 また、再帰関数が正しく実装できていたとしても、数千万回ほどの大量の再帰呼出しを行うようなプログラムでは 実行時エラーが発生することがあります。
次のプログラムは、ベースケースを実装していないため正しく動作しない例です。
#include <bits/stdc++.h> using namespace std; // 0からnまでの総和を計算し、途中結果を出力する int sum(int n) { // ベースケースが実装されていないので止まらない! // 再帰ステップ int result = sum(n - 1) + n; cout << "sum(" << n << ") = " << result << endl; // 途中結果を出力する return result; } int main() { // 無限に再帰呼び出しが起こる cout << sum(100) << endl; }
実行結果の例
終了コード | 139 |
実行時間 | 218 ms |
メモリ | 263296 KB |
終了コードの139はプログラムが正しく終了しなかったことを意味しています。
高度な話になりますが、関数呼び出しを行うときにメモリを消費します。 プログラムを実行しているコンピュータのメモリには限りがあるので、再帰呼び出しが多すぎるとメモリが足りなくなってしまいます。 メモリが足りなくなるとそれ以上プログラムを実行できなくなり、実行時エラーが起こります。 この現象をスタックオーバーフローといいます。 コードテストで実行したときに終了コードが139となった場合は、スタックオーバーフローを疑いましょう。
再帰関数を実装するときは、再帰呼び出しをしすぎると実行時エラーが起こる可能性があることを頭の片隅に置いておくようにしましょう。 スタックオーバーフローを避けるために、ループ構文で繰り返し処理を書き直す必要がある場合もあります。
細かい話
相互再帰
2つ以上の関数が相互に呼び出しあって再帰の形になっているものを相互再帰といいます。
次のプログラムを見てください。
#include <bits/stdc++.h> using namespace std; // プロトタイプ宣言 (1.15.関数「細かい話」を参照) bool is_even(int); bool is_odd(int); // nが偶数かを判定する bool is_even(int n) { // ベースケース if (n == 0) { return true; } // 再帰ステップ return is_odd(n - 1); // n-1 が奇数なら、nは偶数 } // nが奇数かを判定する bool is_odd(int n) { // ベースケース if (n == 0) { return false; } // 再帰ステップ return is_even(n - 1); // n-1 が偶数なら、nは奇数 } int main() { cout << is_even(4) << endl; // 1 cout << is_odd(5) << endl; // 1 cout << is_even(3) << endl; // 0 }
実行結果
1 1 0
まず、is_even
を見てください。再帰ステップでis_odd
を呼び出しています。
一方is_odd
の再帰ステップではis_even
を呼び出しています。
相互再帰では、「その関数の後ろで定義される別の関数」を呼び出すことになるので、プロトタイプ宣言が必須です。 プロトタイプ宣言については、1.15.関数の「細かい話」を参照してください。
上のプログラムの場合はis_even
を先に定義しているので、is_odd
のプロトタイプ宣言があれば十分ですが、分かりやすさのために両方のプロトタイプ宣言を書いています。
相互再帰はプログラムの動作が複雑になりますが、 通常の再帰関数と同様に「再帰呼出しの連鎖に終わりがある」という条件を満たしていれば動作します。
発展的な例
途中で出力する例
クリックで開く
次のプログラムは再帰関数`func`は、「引数のnを1減らして再帰呼出しをn=0になるまで行い、呼び出し履歴を出力する」関数です。 少し複雑ですが、どのように実行されるかを追ってみてください。#include <bits/stdc++.h> using namespace std; // num個分のスペースからなる文字列を返す (字下げに用いる) string space(int num) { string ret = ""; for (int i = 0; i < num; i++) { ret += " "; } return ret; } // 呼び出しの深さに応じて字下げし、関数の開始時点であるというメッセージを出力 void print_in(int n, int depth) { cout << space(depth * 4) << "func(" << n << ", " << depth << ") in" << endl; } // 呼び出しの深さに応じて字下げし、関数の終了時点であるというメッセージを出力 void print_out(int n, int depth) { cout << space(depth * 4) << "func(" << n << ", " << depth << ") out" << endl; } // n: 何回の再帰呼出しを行うか // depth: 呼び出しの深さ(何回目の再帰呼び出しか) void func(int n, int depth) { // ベースケース if (n == 0) { print_in(n, depth); // 開始 print_out(n, depth); // 終了 return; } // 再帰ステップ print_in(n, depth); // 開始 func(n - 1, depth + 1); // 残り回数を1減らし、呼び出しの深さを1増やす print_out(n, depth); // 終了 } int main() { func(3, 0); // 3回の再帰呼び出しを行う, 初めの深さを0とする }##### 実行結果
func(3, 0) in func(2, 1) in func(1, 2) in func(0, 3) in func(0, 3) out func(1, 2) out func(2, 1) out func(3, 0) out
引数の配列を変化させる例
クリックで開く
次のような問題を考えます。 #### 例題 グリッド上の迷路の探索 N \times Nマスのマス目があります。 上からi行目、左からj列目のマスを(i - 1, j - 1 )と表すことにします。 マス目を迷路に見立ててスタート地点から移動を始め、ゴールに到達することができるかを判定するプログラムを作成してください。 スタートは(0, 0)でゴールは(N - 1, N - 1)とします。 マス目には2種類あり、それぞれのマス目はどちらかの種類です。 - 壁マス:そのマスに移動することはできない - 通路マス:そのマスに移動することができる 初めプレイヤーは(0, 0)にいます。(0, 0)、(N - 1, N - 1)は必ず通路マスであるとします。 プレイヤーは今いるマスの上下左右の4方向に隣合うマスのうち、通路マスであるようなマスに移動することができます。 斜めに移動したり、壁マスの中に移動したりすることはできません。また、N \times Nマスの範囲外へ移動することもできません。 移動を繰り返すことでゴールマスである(N - 1, N - 1)に到達することができるなら`Yes`を、そうでないなら`No`を出力するプログラムを作成してください。 各マスがどちらの種類であるかは文字列の配列として入力され、`.`は通路マスを表し、`#`は壁マスを表すとします。 一行目に迷路の大きさNが入力され、2行目以降に迷路のマス目が入力されます。 ##### 入力例13 .## ... ##.##### 出力例1
Yesこの迷路は、(0, 0)→(1, 0)→(1, 1)→(1, 2)→(2, 2)と移動することによってゴールすることができるので、`Yes`を出力します。 ##### 入力例2
4 .### .### .### #...##### 出力例2
Noまた、次の迷路はスタートからゴールまで移動する方法が存在しないので、`No`を出力します。
クリックで入出力例を開く
##### 入力例33 ... ##. ##.##### 出力例3
Yes##### 入力例4
5 ....# ...#. ..#.. .#... #....##### 出力例4
No##### 入力例5
10 ..#.#..### .###.#.##. .##....#.. .##..#.... ....#.##.. #####..... ##.#.###.# #..#.##..# ...####.## #.#.###...##### 出力例5
Yes
解説
このようなマス目の上での移動を扱うときに、単純なループ構文では書くことが難しいです。 しかし、再帰関数を使うと比較的簡単に書くことができます。
解答例
#include <bits/stdc++.h> using namespace std; // 正しい移動かを調べる (y, x)が移動先 bool is_valid_move(vector<string> &board, vector<vector<bool>> &checked, int x, int y) { int N = board.size(); // 移動先がマス目の外である場合 if (x <= -1 || x >= N || y <= -1 || y >= N) { return false; } // 移動先が壁マス if (board.at(y).at(x) == '#') { return false; } // 既に調べているマスへの移動は調べないのでfalseを返す if (checked.at(y).at(x)) { return false; } // それ以外なら正しい移動 return true; } // (y, x)にいる状態からゴールに到達できるか // board: マス目の種類 // checked: そのマスを既に調べたかを持つ二次元配列 bool reachable(vector<string> &board, vector<vector<bool>> &checked, int x, int y) { int N = board.size(); // ベースケース if (x == N - 1 && y == N - 1) { // ゴールにいる状態 return true; } // 再帰ステップ checked.at(y).at(x) = true; // 既に調べているという状態に変えておく // 「上」「右」「下」「左」のいずれかの移動でゴールに到達できるか? bool result = false; // 上へ移動したマスからゴールに到達できるか? if (is_valid_move(board, checked, x, y - 1) && reachable(board, checked, x, y - 1)) { result = true; } // 右へ移動したマスからゴールに到達できるか? if (is_valid_move(board, checked, x + 1, y) && reachable(board, checked, x + 1, y)) { result = true; } // 下へ移動したマスからゴールに到達できるか? if (is_valid_move(board, checked, x, y + 1) && reachable(board, checked, x, y + 1)) { result = true; } // 左へ移動したマスからゴールに到達できるか? if (is_valid_move(board, checked, x - 1, y) && reachable(board, checked, x - 1, y)) { result = true; } return result; } int main() { int N; cin >> N; // マス目の状態を受け取る vector<string> board(N); for (int i = 0; i < N; i++) { cin >> board.at(i); } // 既にそのマスを調べたかを保持する二次元配列 vector<vector<bool>> checked(N, vector<bool>(N, false)); // false(まだ調べていない)で初期化しておく // (0, 0) からゴールまで到達できるか? if (reachable(board, checked, 0, 0)) { cout << "Yes" << endl; } else { cout << "No" << endl; } }
is_valid_move
関数は、あるマスへ移動することができるかを判定する関数です。
範囲外へ出るような移動や、壁マスへの移動をチェックしています。
reachable
関数は再帰関数になっていて、あるマスからゴールまで到達可能かを調べる関数です。
ベースケースは次のようになっています。
if (x == N - 1 && y == N - 1) { // ゴールにいる状態 return true; }
既にゴールしているのでtrueを返しています。
再帰ステップは次のようになっています。
checked.at(y).at(x) = true; // 既に調べているという状態に変えておく // 「上」「右」「下」「左」のいずれかの移動でゴールに到達できるか? bool result = false; // 上へ移動したマスからゴールに到達できるか? if (is_valid_move(board, checked, x, y - 1) && reachable(board, checked, x, y - 1)) { result = true; } // 右へ移動したマスからゴールに到達できるか? if (is_valid_move(board, checked, x + 1, y) && reachable(board, checked, x + 1, y)) { result = true; } // 下へ移動したマスからゴールに到達できるか? if (is_valid_move(board, checked, x, y + 1) && reachable(board, checked, x, y + 1)) { result = true; } // 左へ移動したマスからゴールに到達できるか? if (is_valid_move(board, checked, x - 1, y) && reachable(board, checked, x - 1, y)) { result = true; } return result;
上下左右への移動を行えるかを確認して移動できるなら、「移動した先からゴールまで到達できるか」を調べています。
無限ループを防ぐために、一度調べたマス目を再び調べることがないようにする必要があります。
あるマスaから、隣接するマスbへ移動できるということは、bからaへも移動できることになります。 もし既に調べたマスを調べることができてしまうと、 「aからゴール可能か」を調べるために「bからゴール可能か」を調べ、そのためにまた「aからゴール可能か」を調べる…… というように無限ループが起こってしまいます。
vector<vector<bool>> checked
は、既に調べられているかを表すN \times Nの二次元配列です。
これによって既に調べられているマスは調べないようにしています。
このように、引数の配列を変化させながら再帰呼び出しをすることもあります。
演習問題
リンク先の問題を解いてください。
ABC/ARCの問題
ここまでの知識で解ける問題をAtCoder Beginner Contest / AtCoder Regular Contestの過去問題から紹介します。 練習問題だけでは物足りない人は是非挑戦してみてください。
ヒントと解答例を用意しました。参考にしてください。
クリックでヒントを開く
まずは、「すべての陸地マスが繋がっている」かを調べる関数を作ります。 「すべての陸地マスが繋がっている」を言い換えると「ある1つの陸地マスから上下左右に移動することを繰り返して、すべての陸地マスに到達できる」となります。 これを調べるのは、発展的な例の「グリッド上の迷路の探索」を応用することで実装できます。vector<vector<bool>> checked(10, vector<bool>(10, false)); // 陸地マスを1つ探す int y, x; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (board.at(i).at(j) == 'o') { y = i; x = j; break; } } } /* 引数: 盤面, チェック二次元配列, y座標, x座標*/ fill_island(board, checked, y, x); // (y, x)から到達できるすべての陸地マスのcheckedをtrueにする bool ok = true; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (board.at(i).at(j) == 'o') { if (!check.at(i).at(j)) { // 到達できていない陸地マスがある ok = false; } } } } // ok == true なら全ての陸地マスは繋がっている
クリックで解答例を開く
#include <bits/stdc++.h> using namespace std; // (y, x)から到達できるすべての陸地マスのcheckedをtrueにする void fill_island(vector<vector<char>> &board, vector<vector<bool>> &checked, int y, int x) { if (y < 0 || x < 0 || y >= 10 || x >= 10) return; if (board.at(y).at(x) == 'x') return; if (checked.at(y).at(x)) return; checked.at(y).at(x) = true; // 既に調べているという状態に変えておく fill_island(board, checked, y - 1, x ); // 上 fill_island(board, checked, y , x + 1); // 右 fill_island(board, checked, y + 1, x ); // 下 fill_island(board, checked, y , x - 1); // 左 } bool check_connected(vector<vector<char>> &board) { vector<vector<bool>> checked(10, vector<bool>(10, false)); // 陸地マスを1つ探す int y, x; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (board.at(i).at(j) == 'o') { y = i; x = j; break; } } } /* 引数: 盤面, チェック二次元配列, y座標, x座標*/ fill_island(board, checked, y, x); // (y, x)から到達できるすべての陸地マスのcheckedをtrueにする bool ok = true; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (board.at(i).at(j) == 'o') { if (!checked.at(i).at(j)) { // 到達できていない陸地マスがある ok = false; } } } } // ok == true なら全ての陸地マスは繋がっている return ok; } int main() { vector<vector<char>> board(10, vector<char>(10)); for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { cin >> board.at(i).at(j); } } for (int y = 0; y < 10; y++) { for (int x = 0; x < 10; x++) { if (board.at(y).at(x) == 'o') continue; // (y, x)は海のマス // ここを埋め立てたと仮定して、島が1つになるかを判定 board.at(y).at(x) = 'o'; // 埋め立てたと仮定する if (check_connected(board)) { cout << "YES" << endl; return 0; } board.at(y).at(x) = 'x'; // 戻す } } cout << "NO" << endl; }
「グリッド上の迷路の探索」とほとんど同じ問題です。
これ以降の問題は例題で扱った問題とは少し異なっています。 3.05.ビット演算で説明しているビット全探索を用いることで、再帰関数無しで解くこともできます。