再帰のメモ : PHPで実装

Tweet

Pocket

再帰を使うと複雑な処理を簡単な処理で実現できる。

再帰呼出し（さいきよびだし、英 recursive call）は、プログラミング技法の一つである。

手続きや関数（第一級関数）といった概念をもつプログラミング言語では、ある手続き中で再びその手続き自身を呼び出すことを認める場合が多い。
これを再帰呼出しといい、階乗計算やフィボナッチ数列のように、本来再帰的な構造をもつアルゴリズム（再帰的アルゴリズム）を記述するのに適している。

» 再帰 – Wikipedia

» 自然数列の和 -ループ・再帰・漸化式- : JavaScript(2010.12.07 追記)。

階乗

<?php
// 階乗(factorial) n! = n × (n-1) × (n-2) × ・・・ × 2 × 1,  0! = 1
class Factorial
{
    public function calc($n)
    {
        if ($n === 0) {
            return 1;
        } else {
            return $n * $this->calc($n - 1);
        }
    }
}
$o = new Factorial();
$result = $o->calc(10);
echo $result; // 実行結果 3628800

フィボナッチ数列

再帰を使うとコードは簡便になる。その代わりに処理が膨大になることが多い。この点は注意する必要がある。その対策としてメモ化を使う例をフィボナッチ数列で考える。

<?php
// 0, 1, 2, 3, 4, 5,  6,  7,  8,  9...自然数に0を含める
// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...フィボナッチ数列の初項を1とする(単なる便宜上)
function fibonacci($n)
{
    if ($n < 2) {
        return 1;
    }

    return call_user_func('fibonacci', $n - 1) + call_user_func('fibonacci', $n - 2);

}
echo fibonacci(9); // 55

メモ化

<?php
// 0, 1, 2, 3, 4, 5,  6,  7,  8,  9...自然数に0を含める
// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...フィボナッチ数列の初項を1とする(単なる便宜上)
function fibonacci($n)
{
    global $memo;
    if ($n === 0 || $n === 1) {
        $memo[$n] = 1;

        return 1;
    }

    if (isset($memo[$n])) {
        return $memo[$n];
    }
    $memo[$n] = call_user_func('fibonacci', $n - 2) + call_user_func('fibonacci', $n - 1);

    return $memo[$n];

}

echo fibonacci(9);

フィボナッチ数列の例は書き書籍を参考にしています。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

ハノイの塔 JavaScript

var hanoi = function (n, x, y, z) {
    if (n > 0) { 
        hanoi(n-1, x, z, y);
        console.log("円盤" + n +　" : " +  x + "⇒" + y + "へ移動");
        hanoi(n-1,z,y,x);
   }
}
hanoi(4, "A", "B", "C");

処理が爆発的に増えるので試す場合は6ぐらいにする。