再帰関数入門・全列挙編
競技プログラミングをそれなりに続けてきたが、いまだに再帰関数について全く理解していないので、ここら辺で一つ学んでおこうと思い、この記事を書くことにした。
学習に使うのは以下の問題である。
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の値をそのままにして処理した。