こんにちはみなさん
再帰関数っていいですよね。
こう、厨二心をくすぐられるもので、「ループとかダサいわー、再帰関数でシュッと書けるわー」なんて、しょうもないことを考えていたものです。
しかし、再帰関数を乱用すると、とんでもないことになるかもしれません。
そんな事象を簡単に紹介し、また、メモ化を使った最適化を実践してみましょう。
Fibonacci 数列
私の記事によく出てくる(?)Fibonacci 数列です。Fibonacci 数列の定義は以下の漸化式になります。
a_n = a_{n-1} + a_{n-2}
\ \ (a_0 = a_1 = 1)
例えば、$a_2 = a_1 + a_0 = 2$、$a_3 = a_2 + a_1 = 3$となります。
よくプログラミングの再帰関数の例として出てくる数列ですね。
実装
Fibonacci 数列をそのままPHPで実装してみましょう。
<?php
function fibo(int $n): int
{
$now = $p1 = $p2 = 1;
for ($i = 1; $i < $n; $i++) {
$now = $p1 + $p2;
$p2 = $p1;
$p1 = $now;
}
return $now;
}
こちらは普通のループを使った処理です。
一方、再帰関数を使うと以下のように書けます。
<?php
function fibo(int $n): int
{
if ($n == 0 or $n == 1) {
return 1;
}
return fibo($n - 1) + fibo($n - 2);
}
これらを使うためのテストツールを用意しておきます。
<?php
require $argv[1] . '.php';
echo fibo($argv[2]) . "\n";
これを使って適当な数値で時間計測してみましょう。
時間計測
まず、各々に$n = 10$を代入して動かしてみましょう。
$ time php use.php fibo 10
89
real 0m1.011s
user 0m0.012s
sys 0m0.013s
$ time php use.php fibo2 10
89
real 0m1.085s
user 0m0.014s
sys 0m0.013s
両者、性能に殆ど差はないですね。
次に$n = 34$のときの時間を計測してみます。
$ time php use.php fibo 34
9227465
real 0m1.000s
user 0m0.012s
sys 0m0.015s
$ time php use.php fibo2 34
9227465
real 0m2.038s
user 0m0.014s
sys 0m0.014s
性能に顕著な差が出てきます。
以降、$n$の値を上げるごとに、飛躍的に実行時間が伸びていきます。
再帰関数の重複呼び出し
再帰関数の場合、何回fibo関数が呼ばれるでしょうか？
ちょっとしたトリックを使って、呼び出し回数を計測します。
<?php
class Count {
public static $count = 0;
}
function fibo(int $n): int
{
Count::$count++;
if ($n == 0 or $n == 1) {
return 1;
}
return fibo($n - 1) + fibo($n - 2);
}
もっといいやり方があるかと思いますが、これで呼び出し回数を調べてみましょう。
テストツールもちょっと書き換えます。
<?php
require $argv[1] . '.php';
echo fibo($argv[2]) . "\n";
echo 'call count: '. Count::$count . "\n";
早速動かしてみましょう。
$ php use.php fibo2 1
1
call count: 1
$ php use.php fibo2 2
2
call count: 3
$ php use.php fibo2 3
3
call count: 5
$ php use.php fibo2 4
5
call count: 9
$ php use.php fibo2 5
8
call count: 15
呼び出し回数がどんどん増えていますね。
$n$の値をさらに増やしてみましょう。
php use.php fibo2 20
10946
call count: 21891
php use.php fibo2 30
1346269
call count: 2692537
php use.php fibo2 34
9227465
call count: 18454929
もはや呼び出し回数が性能を圧迫するまでになっています。
原因分析
呼び出し回数が飛躍的に増加している要因はなんでしょうか。
例えば$n=4$のとき、$a_4 = a_3 + a_2$ですが、$a_3$を求めるために、$a_3 = a_2 + a_1$という計算をします。
つまり、$a_2$を求めるfibo関数が２回呼び出されているということです。
以下に、$n=5$のときの呼び出し図を示してみました。
このツリーを見ると、$n=3$が2回、$n=2$は3回、重複して呼び出されています。$n$が大きくなるにつれ、この重複呼び出しされる関数と重複呼び出し回数が増えていくということです。
逆に、この重複呼び出しをしないようにうまく実装してあげれば、再帰関数でも性能をあげられるかもしれません。
典型的な手法としては、一度呼び出した値$n$に対する関数の値を記録しておき、再度同じ値で呼び出されたときには、関数を走らせず、記録した値を使用するという方法があります。
これがメモ化とか呼ばれています。
メモ化による解決
メモ化っていうのは、一度実施された計算結果を覚えておいて、再度呼ばれたときには、その結果を返すようにするというものです。
実装はとても簡単です。
<?php
class Count {
public static $count = 0;
}
function fibo(int $n): int
{
Count::$count++;
// 一度計算済みであればその値を返す
static $result = [];
if (isset($result[$n])) {
return $result[$n];
}
if ($n == 0 or $n == 1) {
return 1;
}
// 計算値をstatic変数に入れる
$result[$n] = fibo($n - 1) + fibo($n - 2);
return $result[$n];
}
(もうループで書いていいんじゃないかな)
PHPにはstatic変数があります。
これはその関数の中で一度だけ初期化され、以降、その変数は処理が終了しても保持され、再度関数が呼び出された際に、前回設定された値が代入された状態になっています。
つまり、fibo(2)が呼ばれると、$result[2] = 2がセットされ、以降fibo(2)が呼ばれると、関数の実処理を行わず、$result[2]の値を返すようになります。
すると、先程見た処理のツリーから、一度呼び出された値の呼び出しについては、以降の関数処理がなくなるため、処理のツリーが以下のように改善されます。
実際に呼び出し回数を見てみましょう。
$ php use.php fibo2 5
8
call count: 9
呼び出し回数が15->9になりました。
また、より大きな値でも検証してみましょう。
$ php use.php fibo2 30
1346269
call count: 59
$ php use.php fibo2 34
9227465
call count: 67
$ php use.php fibo2 40
165580141
call count: 79
呼び出し回数が大きく改善されています。
$n=40$なんて、メモ化なしの場合、そもそもいつ値が返ってくるかわからん状態になっていたので、大きな改良となっています。
まとめ
再帰関数を使って実装するときには、重複呼び出しによる性能悪化を考慮に入れておき、メモ化などで性能への影響を抑えるといいよっていう話でした。
まあ、今回程度のものは普通にループにしてしまったほうが早いんですが、やっぱり再帰関数使いたいなぁってなったら、思い出してもらえるとよいかと思います。
今回はこんなところです