シンプルな再帰処理による全列挙
問題
C: Brute-force Attack - AtCoder Beginner Contest 029 | AtCoder
解法
問題のタイトル通り虱潰しに出していく。Nの最大値が小さいのでfor文を何重にも書いても良いが、再帰関数を用いて書いてみる。
再帰処理を書くポイント
再帰処理を書く場合以下のポイントを押さえる
再帰処理を使うパターン
再帰を使うパターンは以下の通り。
- 同じ処理を複数回する
- 繰り返し処理中に使用する値は異なる
- １つ前の繰り返し処理で行った結果を元に次の繰り返し処理を行う
今回の問題では、a, b, cの３つの文字の中から毎回どれか１つを選ぶ。それをN回繰り返すというものである。
再起する度に変化するもの
今回の問題では再帰処理を行う度に変化するのは、count(文字数)とpass(パスワード)になる。
これらを再帰関数の引数にする。(hoge(int count, String pass))
再帰を抜ける条件
再帰処理を抜ける条件は、文字数がNに到達した時である。Nに到達した時のpassが求めたいものになる。
再帰処理で求めたいもの
再帰処理で求めたい物を引数に置くパターンと戻り値に置くパターンの２つがある。今回は引数に求めたいもの(pass)が存在するので戻り値はvoidにする。
i回目からi+1回目の再帰を呼ぶ
i番目の処理をhoge(count, pass)とした時に、i+1番目ではhoge(count + 1, pass + word(a,b, cのどれか))となる。
