2つの整数aとb (a ≤ b) について、a, a+1, …, b - 1, bの総和を計算する関数sum_rangeを再帰関数で実装します。

具体的な例を挙げると、sum_range(3, 7)なら、3+4+5+6+7=25なので、25を返します。

1. 「引数」「返り値」「処理内容」を決める

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
}

2. 再帰ステップの実装

「a ∼ bの総和」=「a ∼ (b - 1)の総和」+ bという関係式が成り立ちます。

「a ∼ (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 ∼ bの総和」=「a ∼ aの総和」=「a」となるので、このケースがベースケースになります。

また、2で実装した再帰ステップでは、aは変化せずbは1ずつ減って再帰呼び出しの連鎖が起こります。a ≤ 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 ∼ bの総和」=「a ∼ (b - 1)の総和」+ bという関係式に着目して、sum_range(a, b - 1) + bとbを減らしていく方針で実装しましたが、 「a ∼ bの総和」=「(a + 1) ∼ 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の総和」
}

1. 「引数」「返り値」「処理内容」を決める

// dataの要素の総和を計算する
int array_sum(vector<int> &data) {
}

2. 再帰ステップの実装

「配列の要素の総和」=「配列の先頭の要素」+「配列の2番目以降の要素の総和」

「1番目以降の要素の総和」=「1番目の要素」+「2番目以降の要素の総和」

「2番目以降の要素の総和」=「2番目の要素」+「3番目以降の要素の総和」
「3番目以降の要素の総和」=「3番目の要素」+「4番目以降の要素の総和」
...

「i番目以降の要素の総和」=「i番目の要素」+「i+1番目以降の要素の総和」

1.「引数」「返り値」「処理内容」を決める （やり直し）

// (補助関数)
// 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);
}

2. 再帰ステップの実装 （再）

// (補助関数)
// 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. ベースケースの実装

// (補助関数)
// 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
}

#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

1.「引数」「返り値」「処理内容」を決める

// i ~ N-1の範囲にNの約数が存在するか
bool has_divisor(int N, int i) {
}

2. 再帰ステップの実装 / 3. ベースケースの実装

// 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);
}

#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

#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

#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;

// 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

例題 グリッド上の迷路の探索

入力例1

3
.##
...
##.

出力例1

Yes

入力例2

4
.###
.###
.###
#...

出力例2

No

3
...
##.
##.

Yes

5
....#
...#.
..#..
.#...
#....

No

10
..#.#..###
.###.#.##.
.##....#..
.##..#....
....#.##..
#####.....
##.#.###.#
#..#.##..#
...####.##
#.#.###...

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の二次元配列です。 これによって既に調べられているマスは調べないようにしています。

このように、引数の配列を変化させながら再帰呼び出しをすることもあります。

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;
}