再帰処理ロジック

きっかけ

• 教えてgoo!を見ていたら、このような質問を見つけました。
• http://oshiete1.goo.ne.jp/qa3568212.html

• 既に回答がついていて、いろいろやり方あるなあと読んでいました。
• 質問では「0がn個、1がm個」って定義していて、直接解にするのは難しそうです。
• シンプルに考えたら、桁数は決まっている2進表現のうち、0と1の個数が特定のものを抜き出したら簡単かなと考え、回答してみました。

再帰？

• でも、良く考えたら2進表現、要は0と1のすべての組み合わせを、桁数をパラメータ化して列挙するって、どう組んだらいいのでしょうか。
• なんとなく、「再帰」かなと思うのですが。
• 思えば昔アルゴリズム事典みたいな本でソート処理とかで見かけた程度で、実際に再帰のロジックを書いたことがないことに気づきました。

やってみた

• ググったらサンプルソースがあるだろうと思っていたのですが、簡単すぎて記事にならないのか、探し方が悪いのか、検索してもなかなかマッチする記事を見つけられません。
• というわけで、作ってみました。質問はjavaカテゴリでしたが手元にあるPHPで。
• 出来上がりは短いソースですが、結構がんばりました。なんか、犬が自分の尻尾を追いかけてぐるぐる回るような気持ちです。

サンプルソース

• 呼出は第1パラメータの$ketaです。第2パラメータは再帰用です。

function rekkyo($keta, $str = '')
{
    for ($i=0; $i<2; $i++) {    // 2進表現なので0..1のループ
        if ($keta > 1) {
            // 桁がそろうまで再帰連結していく
            rekkyo($keta - 1, $str . $i);
        } else {
            // 桁が全部そろっているなら表示する
            echo $str . $i . "<br>n";
        }
    }
}

Tweet