PHP
AtCoder
プログラミングコンテスト
再帰呼び出し

問題はこちら

この問題も、標準入力から整数を1つだけ受け取ります。

<?php
    fscanf(STDIN, "%d", $N);

リュカ数を、再帰呼び出しで計算してみましょう。

再帰呼び出しとは、関数自身を呼び出して処理を行う手法です。

\$L[0]は、2です。
\$L[1]は、1です。
\$L[i]は、\$L[i-1]と\$L[i-2]を足したものです。

これをそのまま、実装して行きます。

    function calcL($n) {
        switch ($n) {
            case 0:
                return 2;
                break;
            case 1:
                return 1;
                break;
            default:
                return calcL($n - 1) + calcL($n - 2);
        }
    }

完成しました。それでは、paiza.ioで試しに実行してみます。
やってみると、入力例2の「86」でタイムアウトになってしまいます。
なぜでしょうか?
これは、calcL(86)実行時にcalcL(85)とcalcL(84)が呼び出され、calcL(85)の処理でcalcL(84)とcalcL(83)が呼び出され……となるのですが、1回計算されたcalcL(84)などがあったとしても、それを無視してまた別にcalcL(84)の計算をしようとするので、膨大な量の計算が発生してしまうからです。

……という訳で、一度計算した結果はとっておき、それを利用するように改造します。

    function calcL($n) {
        global $array;
        $array[0] = 2;
        $array[1] = 1;
        if (isset($array[$n])) {
            return $array[$n];
        } else {
            $array[$n] = calcL($n - 1) + calcL($n - 2);
            return $array[$n];
        }
    }

関数のローカル変数は再帰呼び出しの際にスコープの違いにより参照されなくなってしまいますので、グローバルの変数(配列) $array を設定しています。

さきほどのプログラムでは1分経っても答えは返ってきませんが、改造した方のプログラムでは、0.03秒ほどで計算結果が表示されます。

paiza.ioでのURL

AtCoderでの実行結果