再起処理がメモリ食うって本当？を検証してみた

株式会社オズビジョンのユッコ (@terra_yucco) です。
業務内のコードレビューで久々に再帰処理を見かけました。
個人的に、再帰処理は (構文解析など、構造がそれに適したものの用途でない限り) メモリの消費が激しいので使うべきでないと教えられてきましたが、実際どうなのかを計測してみました。

# TL;DR

今回の単純なコードの例では、圧倒的に普通のループのほうがよさげ。
無理に再帰を使う理由が見当たらない。

## 再帰処理
### コード

```php:recursion.php
<?php

$class = new Main();
$class->work();

class Main
{
    public function work()
    {
        echo memory_get_usage(true) . PHP_EOL;
        echo memory_get_usage(false) . PHP_EOL;
        echo memory_get_peak_usage(true) . PHP_EOL;
        echo memory_get_peak_usage(false) . PHP_EOL;
        $this->loop();
        echo memory_get_usage(true) . PHP_EOL;
        echo memory_get_usage(false) . PHP_EOL;
        echo memory_get_peak_usage(true) . PHP_EOL;
        echo memory_get_peak_usage(false) . PHP_EOL;
    }

    private function loop($index = 0)
    {
        if ($index >= 20000) {
           echo '$index=[' . $index . ']' . PHP_EOL;
           return;
        }
        $this->loop($index + 1);
    }
}
```

### 結果 (10 回分)

－|usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|real|user|sys
:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--
min    |262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.334s|0m0.020s|0m0.028s
max    |262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.807s|0m0.060s|0m0.052s
avg    |262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.516s|0m0.034s|0m0.040s
90%Tile|262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.678s|0m0.052s|0m0.048s


#### raw data

usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|real|user|sys
:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.334s|0m0.028s|0m0.040s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.590s|0m0.032s|0m0.048s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.347s|0m0.036s|0m0.036s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.531s|0m0.052s|0m0.032s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.807s|0m0.060s|0m0.048s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.413s|0m0.020s|0m0.028s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.678s|0m0.024s|0m0.048s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.470s|0m0.024s|0m0.028s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.397s|0m0.024s|0m0.040s
262144|230688|262144|238592|3145728|230712|9699328|9575632|0m0.597s|0m0.036s|0m0.052s

## 通常ループ処理

```php:loop.php
<?php

$class = new Main();
$class->work();

class Main
{
    public function work()
    {
        echo memory_get_usage(true) . PHP_EOL;
        echo memory_get_usage(false) . PHP_EOL;
        echo memory_get_peak_usage(true) . PHP_EOL;
        echo memory_get_peak_usage(false) . PHP_EOL;
        $this->loop();
        echo memory_get_usage(true) . PHP_EOL;
        echo memory_get_usage(false) . PHP_EOL;
        echo memory_get_peak_usage(true) . PHP_EOL;
        echo memory_get_peak_usage(false) . PHP_EOL;
    }

    private function loop($index = 0)
    {
        while ($index < 20000) {
            $index++;
        }
        echo '$index=[' . $index . ']' . PHP_EOL;
        return;
    }
}
```


### 結果 (10 回分)

－|usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|real|user|sys
:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--
min|262144|230432|262144|238400|262144|230432|262144|238400|0m0.115s|0m0.016s|0m0.012s
max|262144|230432|262144|238400|262144|230432|262144|238400|0m0.239s|0m0.044s|0m0.044s
avg|262144|230432|262144|238400|262144|230432|262144|238400|0m0.155s|0m0.029s|0m0.026s
90%Tile|262144|230432|262144|238400|262144|230432|262144|238400|0m0.201s|0m0.040s|0m0.036s

#### raw data

usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|real|user|sys
:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--
262144|230432|262144|238400|262144|230432|262144|238400|0m0.166s|0m0.024s|0m0.020s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.239s|0m0.020s|0m0.028s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.201s|0m0.028s|0m0.016s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.189s|0m0.024s|0m0.012s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.115s|0m0.028s|0m0.028s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.130s|0m0.036s|0m0.036s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.117s|0m0.016s|0m0.044s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.129s|0m0.032s|0m0.032s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.134s|0m0.040s|0m0.024s
262144|230432|262144|238400|262144|230432|262144|238400|0m0.132s|0m0.044s|0m0.020s

## 乱暴な比較

統計サンプルとするには少ないですが、とりあえず各々 10 回ずつ実行して比較をしてみました。

### 再起処理 - ループ処理

ほぼ全ての項目で、再起処理の方が利用リソースが多いことがわかります。
時間については議論できるほどのオーダーではないかもしれません。

ただし `memory_get_usage()` 系の関数で取得しているメモリ使用量については、byte 単位とはいえかなりの差が出ています。
だいたい 9 MB くらいでしょうか。
今回の、ただ単にカウントアップした数字を出すだけのプログラムの場合には 9 MB ものメモリを使う価値はないと思いますので、素直にループ処理を書いておくのが正解と言えそうです。

－|usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|usage<br>true<br>after|usage<br>false<br>after|peak<br>true<br>after|peak<br>false<br>after|real|user|sys
:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--
min|0|256|0|192|2883584|280|9437184|9337232|0m0.219s|0m0.004s|0m0.016s
max|0|256|0|192|2883584|280|9437184|9337232|0m0.568s|0m0.016s|0m0.008s
avg|0|256|0|192|2883584|280|9437184|9337232|0m0.361s|0m0.005s|0m0.014s
90%Tile|0|256|0|192|2883584|280|9437184|9337232|0m0.477s|0m0.012s|0m0.012s

## Conclusion

前職の頃、念仏のように聞いていた「再起処理はメモリを食うぞ」を簡易的にですが確認してみました。
業務で見かけたコードはもっとずっと複雑なので、そういうコードで比較ができればもう少し面白い結果になるかもしれません。

良い記事や知見があれば、ぜひ教えていただきたいです！