【競プロ】再帰関数

🕒 2019/10/28 🔄 2023/05/01

ここでは、再帰関数について見ていきます。競プロ記事の一覧はこちら。

📘 目次

再帰関数

プログラミング言語の中に PHP という言語がありますが、これが何の略か知っていますか？　これは「PHP: Hypertext Preprocessor」の頭文字をとったものです（参考：PHP: PHP とはなんでしょう? - Manual）。意味は、「PHPはHTMLのプリプロセッサだ」というものですが、よく見ると、PHP の説明の中に自分自身(=PHP) が入っていますね。

このように、自分自身を定義・説明する中で自分自身が登場することを、再帰(recursion) といいます。例えば、Googleで「再帰」を検索すると次のようになります。

「再帰」の検索結果の中に「再帰」へのリンクがある、というのは、再帰的な検索結果になっていますね。

プログラミングでは、関数を定義するときに、自分自身を呼び出す書き方をすることがあります。このような関数を再帰関数といいます。再帰関数を使うと、コードが短くシンプルになることがあります。以下では、プログラミングで再帰関数をどのように扱うのか、見てみます。

カウントダウン

年越しや大きなイベントの前では、カウントダウンが行われます。3秒前なら、3, 2, 1, 0 と減っていき、10秒前なら、 10, 9, …, 2, 1, 0 と減っていきます。このように表示するプログラムを再帰関数を使って書いてみましょう。

カウントダウンをどの数からスタートするか、を再帰関数の引数にするのが自然でしょう。 3 が渡されたら、 3 を出発点としてカウントダウンをしていくのですが、ここで処理を分割してみましょう。 3 とそれより後に分けてみます。そうすると、"3" と言った後は、 2 から始まるカウントダウンをしていく、と考えることができます。

繰り返すと次のようになります。

「3から始まるカウントダウン」
＝
「3と言う」+「2から始まるカウントダウン」
＝
「3と言う」+「2と言う」+「1から始まるカウントダウン」
＝
「3と言う」+「2と言う」+「1と言う」+「0から始まるカウントダウン」
＝
「3と言う」+「2と言う」+「1と言う」+「0という」

このようにすると、n から始まるカウントダウンは、「 n と言う」+「n - 1 から始まるカウントダウン」と分解できることがわかります。カウントダウンの処理の中に、別のカウントダウンの処理が入っています。ここが再帰に関係している部分です。

これをもとに、countDown という関数を作ると、次のように書くことができます。

#include <iostream>
using namespace std;

void countDown(int n) {
  if (n == 0) {
    cout << 0;
  } else {
    cout << n << ", ";
    countDown(n - 1);
  }
}

int main() {
  int n; cin >> n;
  countDown(n);
  return 0;
}

countDown の中で、自分自身である countDown を呼び出しています。こうするとずっと循環していくような気がしますが、0になったらカウントダウンは終了なので、その場合分けを含めています。3 や 10 などの正の整数を入れて、きちんと動くことを確かめてみましょう。

for文やwhile文との違い

上のコードを見て、for文やwhile文を使った方が楽じゃないか、と思う人もいるでしょう。実際、上のコードは次のように for文を使って書き直すことができます。

#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  for (int i = 0; i < n; i++) {
    cout << (n - i) << ", ";
  }
  cout << 0;
  return 0;
}

while文で書けば、次のようになります。

#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  while (n > 0) cout << n-- << ", ";
  cout << 0;
  return 0;
}

このように、再帰関数で書いた処理は、for文やwhile文で書き換えられることも多いです。

ではなぜわざわざ再帰関数を使うかというと、コードが短くなり、シンプルになることがある、という点があります。例えば、過去に再帰関数で表現できる処理として、ユークリッドの互除法を紹介しました。比較のために、まずは while文で書いたものを見てみましょう。

#include <iostream>
using namespace std;

int gcd(int a, int b) {
  while (a % b != 0) {
    int a2 = a;
    a = b;
    b = a2 % b;
  }
  return b;
}

int main() {
  int a, b;
  cin >> a >> b;
  cout << gcd(a, b);
  return 0;
}

ユークリッドの互除法は、2つの正の整数 x, y の最大公約数を求めるために、y, x % y の最大公約数を求める、というのを繰り返して計算する方法です。処理回数がわからないので、for文では書きにくい（書けなくはないですけど）ので、上では while文で書いています。変数を入れ替える必要があるため、別の変数を持ち出してこなくてはいけません。

再帰関数を使えば、ユークリッドの互除法は次のように書けます。

#include <iostream>
using namespace std;

int gcd(int a, int b) {
  return (a % b)? gcd(b, a % b): b;
}

int main() {
  int a, b;
  cin >> a >> b;
  cout << gcd(a, b);
  return 0;
}

再帰関数では、変数を入れ替える必要はありません。次の関数呼び出しのときに引数を変えていますが、これが変数入れ替えに対応します。変数の入れ替え処理を書かなくていいので、シンプルになりやすいです。

考えている問題について、N 回目の場合と N - 1 回目の場合との関係がわかっている場合、例えば、このユークリッドの互除法や上で見たカウントダウンの場合などでは、再帰関数を使って書けることが多いです。また、中には、再帰処理で書かないとすごく複雑になってしまうようなケースも存在します。今後、再帰関数を使って書ける処理についていくつか見ていくことになります。

一方、for文やwhile文で書いた処理を再帰関数で書き換えられるかどうかは、ケースバイケースです。書き換えられない理由はいくつかありえますが、1つはメモリの問題です。再帰関数を使うと、途中の呼び出しの情報をずっと持ち続けることになるため、何度も呼び出すとメモリをたくさん消費してしまいます。

他には、N 回目の場合と N - 1 回目の場合との関係がはっきりと定義できないケースがある、という原因もありえます。そういう場合は、 for文やwhile文を使うほうがいいでしょう。