再帰関数入門・全列挙編

競技プログラミングをそれなりに続けてきたが、いまだに再帰関数について全く理解していないので、ここら辺で一つ学んでおこうと思い、この記事を書くことにした。

学習に使うのは以下の問題である。
C - Brute-force Attack

要は、「a,b,c」を並べて作ることができる長さnの文字列を全列挙せよ、ということだ。

解説にあったコードを真似てJavaで書いたものが以下のコードになる。

import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		f(n,"");
	}
	
	static void f (int n, String s) {
		if (n ==0) {System.out.println(s);}
		else {
			for (char c='a'; c<='c'; c++) {
				f(n-1,s+c);
			}
		}
	}
}

n=2のときを考えてみる。n=2のとき、この再帰関数の深さは3層である。

f(2,s)　elseの処理
f(1,s)　elseの処理
f(0,s)　ifの処理（出力）

nを減らしながら処理をしていって、nが0になったら完成した文字列を出力、という流れになっているらしい。

次は、nとsに具体的な値を入れて、関数の動作を追ってみることにする。

関数は最初、f(2,"")という形でメインメソッドから呼び出される。これが1層目。

1層目：f(2,"")

nは0ではないので、elseの処理が実行される。1層目の関数からは以下の3つの関数が2層目として呼び出される。

2層目：f(1,""+a), f(1,""+b), f(1,""+c)

nは1なので、elseの処理が実行される。2層目の3つの関数から、それぞれ3つの関数が3層目として呼び出される。

3層目：f(0,a+a), f(0,a+b), f(0,a+c)　f(0,b+a), f(0,b+b), f(0,b+c)　f(0,c+a), f(0,c+b), f(0,c+c)

3層目の9つの関数は、nが0である。よって、ifのほうの出力処理が実行される。

出力：
aa
ab
ac
ba
bb
bc
ca
cb
cc

3層目の9つの関数が出力処理をすると書いたが、9つが3層目でまとめて処理されるわけではない。

これは上記のコードに、現在のnの値も出力するようにしたプログラムになる。

これを見て分かる通り、nが2で呼び出されるのは最初の一回のみ。次に2層目の1番目の関数が呼び出され、そのまま3層目に入り、3層目の1～3番目の出力処理がされている。つまりこの関数の処理は、一気に最下層まで下りていく「深さ優先探索」の形になっている。

この問題の応用&練習として、「パスワードの候補として考えられる文字列（大文字）と、文字列に含まれる穴の数をすべて列挙せよ」という問題を考えてみることにする。穴の数（表記したときに線で囲まれる部分）はAなら1個、Bなら2個、Cなら0個。

import java.util.*;
import static java.lang.System.*;

public class Test {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		f(n,"",0);
	}
	
	static void f (int n, String s, int m) {
		if (n==0) {System.out.println(s+":"+m);}
		else {
			for (char c='A'; c<='C'; c++) {
				if (c=='A') {f(n-1,s+c,m+1);}
				else if (c=='B') {f(n-1,s+c,m+2);}
				else if (c=='C') {f(n-1,s+c,m);}
			}
		}
	}
}

穴の数を変数mで管理し、ループのAから関数を呼び出すときは+1、Bから呼び出すときは+2、Cから呼び出すときはmの値をそのままにして処理した。