再帰関数はどんなときに嬉しいのか

A. 再帰的な構造を操作するとき

最近なぜか再帰関数に興味を持つ型が多いらしいので、自分なりに説明を書きます。

ケース1: 階乗？

高校でやった算数のテストは常に赤点でしたが、階乗のことは知ってます。

このコードをPHPで書くのは簡単でしょうか。

<?php declare(strict_types=1);

function factorial(int $n): int
{
    $f = 1;
    for ($i = 1 ; $i < $n; $i++) {
        $f *= $i;
    }

    return $f;
}

算数が苦手な私には簡単ではなく、つっかかるポイントがいくつかありました。
forは変数の初期化、継続条件、変数の更新を考えないと書けませんからね。

なので、表にしてみます。

0! = 1                 =   1
1! = 1                 =   1
2! = 1 * 2             =   2
3! = 1 * 2 * 3         =   6 
4! = 1 * 2 * 3 * 4     =  24
5! = 1 * 2 * 3 * 4 * 5 = 120

この表を見ると、1より大きい数に関しては、ひとつ上の行とそっくりです。
具体的には、ひとつ上の行に「その数」を掛け算したものになりますね。

これを変形していくと、こうなります。

5! = 1 * 2 * 3 * 4 * 5
5! = (1! =  1) * 2 * 3 * 4 * 5
5! = (2! =  2) * 3 * 4 * 5
5! = (3! =  6) * 4 * 5
5! = (4! = 24) * 5
5! = 120

なんか似たような構造が何回も出てきました。たまねぎの皮向きのようですね。

要は$n > 1$のとき、$n! = (n-1)! \times n$と表現できますね。
Wikipediaを読むと、$n = 0$と$n = 1$の場合は$1$らしいです。

これをPHPの式として関数に翻訳するのはかんたんです。

<?php declare(strict_types=1);

function _factorial(int $n): int
{
    return ($n > 1) ? _factorial($n - 1) * $n : 1;
}

この問題は、計算を繰り返す、つまりたまねぎの皮を剥く回数が$n$回、つまり変数であることが特徴ですね。
今回の関数は再帰をやめるタイミングを書いてやる必要はありますが、それすら定義通りに書けばいい感じになりました。

ケース2: 入れ子になった配列

以下のような配列を、HTMLの<table>タグに整形する関数を考えてみてください。

$files = [
    'foo.php',
    'bar.php',
    'buz.php',
];

こんなの、PHPが大得意なところです。任せてくださいよ！

<?php

print_files($files);

function print_files(array $files)
{ ?>
<table>
<?php foreach ($files as $i => $f): ?>
    <tr>
        <td><?= htmlspecialchars($i, ENT_QUOTES, 'UTF-8') ?></td>
        <td><?= htmlspecialchars($f, ENT_QUOTES, 'UTF-8') ?></td>
    </tr>
<?php endforeach; ?>
</table>
<?php }

<table>
    <tr>
        <td>0</td>
        <td>foo.php</td>
    </tr>
    <tr>
        <td>1</td>
        <td>bar.php</td>
    </tr>
    <tr>
        <td>2</td>
        <td>buz.php</td>
    </tr>
</table>

簡単ですね。

では、このような構造ならどうでしょう。

<?php

$files = [
    'src' => [
        'foo.php',
        'bar.php',
        'buz.php',
    ],
    'tests' => [
        'FooTest.php',
        'BarTest.php',
        'BuzTest.php',
    ],
];

こんなの簡単です。 foreachをもう一段深くすればいいんでしょ？

print_files($files);

function print_files(array $dirs)
{ ?>
<table>
<?php foreach ($dirs as $dir_name => $files): ?>
    <tr>
        <th><?= htmlspecialchars($dir_name, ENT_QUOTES, 'UTF-8') ?></th>
        <td><table>
            <?php foreach ($files as $i => $f): ?>
            <tr>
                <th><?= htmlspecialchars($i, ENT_QUOTES, 'UTF-8') ?></th>
                <td><?= htmlspecialchars($f, ENT_QUOTES, 'UTF-8') ?></td>
            </tr>
            <?php endforeach; ?>
        </table></td>
    </tr>
<?php endforeach; ?>
</table>
<?php }

みなさん、ご期待の通り「こんなの簡単」はフラグです。

$files = [
    'README.md',
    'src' => [
        'foo.php',
        'bar.php',
        'buz.php',
    ],
    'tests' => [
        'FooTest.php',
        'BarTest.php',
        'BuzTest.php',
    ],
    'vendor' => [
        'foo' => [
            'bar' => [
                'hoge' => [
                    'README.php',
                    'fuga' => [
                        'piyo' => [
                            'piyopiyo.php'
                        ],
                    ],
                ],
            ]
        ]
    ],
];

これをさっきと同じ方法で<table>にしようとしたら、何重ループにすればいいの？ どうせファイルは増えたり減ったりするんでしょ？ よくわかんないや。

解法

ここで立ち止まって、仕様を日本語で書いてみます。

• ファイルとディレクトリの構造をPHPの変数として表現したい
• ファイル名は文字列として表現する
• ディレクトリは配列として表現し、中にディレクトリとファイルを含めることができる

ディレクトリの中にはディレクトリがある… これは何回むけばいいのかわからない、たまねぎの皮むきの予感！
正解にはむく回数は手で数えればわかるのですが、7回ネストしたforeachなんて絶対に書きたくないでござる。

そう、何回むけばいいのかわからない構造に対する処理は、再帰関数の出番です。

print_files($files);

function print_files(array $files)
{ ?>
<table>
<?php foreach ($files as $i => $f): ?>
    <tr>
        <th><?= htmlspecialchars($i, ENT_QUOTES, 'UTF-8') ?></th>
        <?php if (is_string($f)): ?>
            <td><?= htmlspecialchars($f, ENT_QUOTES, 'UTF-8') ?></td>
        <?php else: ?>
            <td>
                <?php print_files($f) ?>
            </td>
        <?php endif; ?>
    </tr>
<?php endforeach; ?>
</table>
<?php }

意外とシンプルになりましたね。

まとめ

再帰関数は、再帰的構造、つまり「何回もたまねぎの皮むきをしなければいけない」ような問題の解決に向きます。

しかし、数式のようなものを再帰関数で表現するのが良いアプローチと言うと、数式に近い表現で書けるのですっきりするのですが、実はあんまり良くないことも結構あります。

例としてはPHPのような言語でフィボナッチ数列の要素を再帰関数として実装することはよく知られた事実です、気になるひとは一度調べて実装してみてください。玉ねぎをむくよりもパフォーマンスにすぐれた解決方法があることもあります。フィボナッチ数列に関しては私は皮むきをせずにジェネレータで実装するのが一推しです。

普通のwhileとかforでもありえる話なのですが、再帰関数で実装するとよくわからない条件で無限ループすることがたまにあります。無限ループでなくとも、ある程度に深くなったら計算を打ち切るといったアプローチをしなければいけないことがあるかもしれません。

また、PHPには再帰関数を書かなくても再帰的な処理をする方法はいくつもあって、array_reduce()やarray_walk_recursive()、SPLイテレータ などです。暇なら調べてみてください。まあそれがわかりやすいとも限らないのですけど。 PHPを極めてキミだけのリーダブルコードを見つけだせ！

再帰関数を実装して納得したい読者への課題

あなたが開発しているPHPプロジェクトのディレクトリ名を文字列で渡すと、そのディレクトリに含まれるPHPファイル(子ディレクトリを含む)の合計行数をカウントするPHPスクリプトを書いてみてください。