ループと再帰の関係

プログラマなら誰もが知っている再帰ですが、よくC言語のポインタと並んで初心者がよくつまづく概念としても有名(?）です。今回はこの再帰(特に末尾再帰について)と基本的な制御構造の一つであるループとの関係について考えてみます。

ループ構文というのは大抵の言語に存在する制御構造ですが、世の中にはループ構文が存在しない言語もたくさんあります(gotoでジャンプしてるわけではありませんよ)。このような言語ではループの代わりに再帰呼び出しを使います。一見するとループと再帰呼び出しは別物のように見えますが、よーく見ていくと実はループと再帰呼び出し(特に末尾再帰)はとてもよく似ているのです。

例えば、次のようなループである範囲の整数を順に標準出力に出力するメソッドは

	void loopSample(int min, int max) {

		for (int i = min; i < max; i++) {

			System.out.println(i);
		}
	}

ループを使わないで、これと同じ動作をするメソッドは次のように書けます。

void recSample(int min, int max) {

		if (min < max) {

			System.out.println(min);

			recSample(min + 1, max);
		}
	}

これは末尾再帰という形で再帰呼び出しをすることでループと同等のコードを再帰で記述しています。

では末尾再帰はただの再帰とどう違うのでしょうか。

重複のない順列の個数を求めるループと(末尾再帰でない)普通の再帰呼び出しと末尾呼び出しのコードを比較してみましょう。

①ループ

	int loopPermutation(int n, int m) {
		int result = 1;
		for (int i = m; i > n; i--) {

			result *= i;
		}
		return result;
	}

②再帰

	int recPermutation(int n, int m) {
		if (n >= m) {

			return 1;
		} else {
			return m * recPermutation(n, m - 1);
		}
	}

③末尾再帰

	int tailRecPermutation(int n, int m, int acc) {
		if (n <= m) {

			return acc;
		} else {
			return tailRecPermutation(n - 1, m, n * acc);
		}
	}

重複のない順列の個数というのは、n個の異なる要素からm個の要素を選び出した順列の個数で nPm と表されます(中学で習いましたね)。この値はnの階乗を(n-m)の階乗で割ることで求めることができるのですが、これは n * (n - 1) * ... * (m + 2) * (m + 1)、つまりnから(m+1)までの積求めることができます。

このアルゴリズムをループ、再帰で記述すればそれぞれ①、②のようになることでしょう。②の再帰版は①と同様に動作しますが、再帰が深くなるとスタックオーバーフローを起こします。これは引数やローカル変数をスタックに積んでメソッドを呼び出すためです。

これに対して③の末尾再帰版は引数が一つ増えており、この引数で計算結果を引き回しています。

これらのコードがどのように動作するかを見るために、上の3つのメソッドを実装しているクラスを継承して次のようなコードを実装して動かしてみます。

@Override
		int loopPermutation(int n, int m) {

			int result = 1;

			for (int i = n; i > m; i--) {

				result *= i;

				System.out.println("Loop loopPermutation(" 
                                                  + this.count + "): i = " + i + ",
                                                              result = " + result);

				this.count++;
			}
			this.count = 0;
			return result;

		}		
		@Override

		int recPermutation(int n, int m) {

			System.out.println(indent(this.count) + "Call 
                                      recPermutation(" + this.count + "): 
                                                  n = " + n + ", m = " + m);

			this.count++;

			int result = super.recPermutation(n, m);

			this.count--;

			System.out.println(indent(this.count) + "Return
                                      recPermutation(" + this.count + "): 
                                                        result = " + result);

			return result;

		}
		@Override

		int tailRecPermutation(int n, int m, int acc) {

			System.out.println(indent(this.count) + "Call 
                                     tailRecPermutation(" + this.count + "): 
                                 n = " + n + ", m = " + m + ", acc = " + acc);

			this.count++;

			int result = super.tailRecPermutation(n, m, acc);

			this.count--;

			System.out.println(indent(this.count) + 
                                "Return tailRecPermutation(" + this.count + "):
                                                          result = " + result);

			return result;
		}

このコードを実行すると次のような出力が得られます。

①loopPermutation:

Loop loopPermutation(0): i = 4, result = 4

Loop loopPermutation(1): i = 3, result = 12

②recPermutation:

Call recPermutation(0): n = 4, m = 2

Call recPermutation(1): n = 3, m = 2

Call recPermutation(2): n = 2, m = 2

Return recPermutation(2): result = 1

Return recPermutation(1): result = 3

Return recPermutation(0): result = 12

③tailRecPermutation:

Call tailRecPermutation(0): n = 4, m = 2, acc = 1

Call tailRecPermutation(1): n = 3, m = 2, acc = 4

Call tailRecPermutation(2): n = 2, m = 2, acc = 12

Return tailRecPermutation(2): result = 12

Return tailRecPermutation(1): result = 12

Return tailRecPermutation(0): result = 12

②と③のReturnに注目してください。②では呼び出しから返るたびに返り値が異なっています。これに対して③では返り値がすべて同じです。これにより③のコードはReturnするコードを削除することができるようになり、またスタックに引数やローカル変数を保存しておく必要がなくなり、最適化することで結局ループと同じになるのです。

でも③の末尾再帰のコードを大きな数値で実行してみるとスタックオーバーフローするじゃないか、と言う人も居るかもしれません。その通りです。残念ながらJavaはこのような末尾再帰の最適化はしてくれないのでした。(何)

EeBlog(テクニカルブログ)

ループと再帰の関係