Skip to content

Instantly share code, notes, and snippets.

@nihemak
Created July 23, 2013 15:56
Show Gist options
  • Save nihemak/6063564 to your computer and use it in GitHub Desktop.
Save nihemak/6063564 to your computer and use it in GitHub Desktop.
<?php
# 継続渡しスタイルの末尾再帰関数をwhile形式に変換して実行する関数
function tco(array $xs, $f) {
list($ys, $in, $run) = [[], false, false];
return call_user_func_array($g = function() use($f, &$ys, &$in, &$run) {
$zs = func_get_args();
if ($in) {
$ys = $zs;
$run = true;
return null;
}
$in = true;
do {
$run = false;
$r = call_user_func_array($f, $zs);
$zs = $ys;
}
while ($run);
return $r;
},
array_merge([$g], $xs));
}
# 例えば、0から指定したnまでの和を求める末尾再帰関数は通常の定義だと次のようになる。
function mysum($n, $acc = 0) {
return $n == 0 ? $acc : mysum($n - 1, $acc + $n);
}
# これに大きな値を指定するとメモリを大量に消費して最悪の場合スタックオーバーフローする。
# echo mysum(4000000). "\n";
# 同じ事をtco関数で定義すると次のようになる。
function mysum2($n) {
return tco([$n], function($f, $n, $acc = 0) {
return $n == 0 ? $acc : $f($f, $n - 1, $acc + $n);
});
}
# こちらはメモリをあまり消費せずスタックオーバーフローにならないはず。
echo mysum2(4000000). "\n";
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment