再帰関数で部分集合を全列挙する

以下の記事では、ビット全探索による部分集合の全列挙を勉強しました。

jpliterature.hatenablog.com

今回の記事では、同じことを再帰関数でやってみようと思います。

さて、再帰関数で部分集合を全列挙するにあたり、こんな問題を作ってみました。

問題文

幸本君の住んでいる街にはイルミネーションがあり、夜になると、横一直線に並んでいるライトが点いたり消えたりして、たいへん綺麗である。すべてのライトが消えるときもあれば、1つおきに点灯することもあるし、もちろん、すべて点灯することもある。イルミネーションに目がない幸本君は、毎日のようにこのライトを見に行っていたが、ある日、ライトが点灯するパターンがどれだけあるのか気になった。幸本君の友達で、再帰関数を考えることが趣味のあなたは、幸本君の代わりにライトが点灯するパターンをすべて列挙してください。

制約

1 <= N <= 2000msに間に合うくらい

入力

数値Nが入力として与えられる。

出力

ライトが点いている状態を "o" 、ライトが消えている状態を "x" として、N個のライトが点灯するパターンを全て列挙せよ。なお、列挙する順序は問わない。

入力例1

1

出力例1

o
x

ライトは1つしかないので、点灯しているか消灯しているかの2パターンしかありません。

入力例2

3

出力例2

xxx
oxx
xox
xxo
oox
xoo
oxo
ooo

ACコード（想定）

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		dfs(sc.nextInt(), new StringBuilder(""));
		
	}
	
	
	static void dfs (int n, StringBuilder sb) {
		if (n == 0) {
			System.out.println(sb);
			return;
		}
		dfs(n-1, new StringBuilder(sb).append("x"));
		dfs(n-1, new StringBuilder(sb).append("o"));
	}
	
}

n を終了条件に持ち、n が 0 になるまで、すなわち入力の N が 3 であれば n=3,2,1 と3回まで、空文字列に o か x どちらかを結合する再帰関数です。n が 0 になったら、文字列を出力して再帰を終了します。この終了条件をきちんと書かないと、無限に再帰してしまい、スタックオーバーフローのエラーを起こしてしまうので注意が必要です。

書いてから気づきましたが、ビット全探索よりもずいぶんシンプルに書けるんですね。動作がわかりやすいからビット全探索を好んで使っていましたが、これからは再帰関数派になろうかしら。ま、それはともかく、このプログラムを N=4 で動かしたときの出力は以下のようになります。

xxxx
xxxo
xxox
xxoo
xoxx
xoxo
xoox
xooo
oxxx
oxxo
oxox
oxoo
ooxx
ooxo
ooox
oooo

o の位置が何か模様のように見えて、数学的な美しさを感じます。このようにして再帰関数では、短い記述で簡単に全列挙の処理をおこなうことができます。再帰関数を応用したものにメモ化再帰というものもあるみたいなので、いつか理解できたらそれも記事にしてみたいと思います。