안녕하세요.
회귀 함수라고 할 수 있죠.
이렇게 되면 셰프의 이심을 불러일으키는 것,'순환 따위는 촌스러워 회귀함수로 쓱쓱 쓸 수 있다'같은 것은 무리한 고민이다.
하지만 회귀 함수를 남용하면 예상치 못한 일이 될 수도 있다.
이런 현상들을 간단히 소개한 다음에 필기화의 최적화를 실천해 보세요.

Fibonacci 수열

제 글에 많이 나와요.Fibonacci 수열입니다.Fibonacci 수열의 정의는 다음과 같습니다.

a_n = a_{n-1} + a_{n-2}
\ \  (a_0 = a_1 = 1)

예: $a2 = a_1 + a_0 = 2$、$a_3 = a_2 + a_1=3달러입니다.
프로그램 설계의 귀속 함수의 예로 자주 나타나는 수열.

이루어지다

그렇게 피바나시 수열을 PHP로 설치하세요.
fibo.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;
}

이것은 일반 순환을 사용하는 처리다.
다른 한편, 귀속 함수를 사용하면 다음과 같은 내용을 쓸 수 있다.
fibo2.php

<?php

function fibo(int $n): int
{
    if ($n == 0 or $n == 1) {
        return 1;
    }

    return fibo($n - 1) + fibo($n - 2);
}

나는 이런 테스트 도구를 사용할 준비를 할 것이다.
use.php

<?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함수라고 몇 번을 부릅니까?
약간의 기교를 사용하여 호출 횟수를 측정하다.
fibo2.php

<?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);
}

나는 더 좋은 방법이 있다고 생각한다. 지금 호출 횟수를 조사해 보자.
나도 테스트 도구를 고쳐 쓰겠다.
use.php

<?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$일 때, $a4 = a_3 + a_2달러,달러 a달러3 = a_2 + a_1달러를 계산하다.
달러2달러fibo 함수가 두 번 호출되었다.
다음은 $n=5달러일 때의 호출도입니다.

이 나무를 보고 두 번 $n=3달러, 세 번 $n=2달러가 중복 호출되었다$n이 증가함에 따라 중복 호출 함수와 중복 호출 횟수도 증가합니다.
반대로 중복 호출을 하지 않기 위해 순조롭게 실시되면 회귀 함수도 성능을 높일 수 있다.
전형적인 방법으로, 호출 값 $n$$$$$$$$$$$$$$$$n의 함수 값을 기록하는 방법이 있는데, 다시 같은 값으로 호출하면 함수를 실행하지 않고 기록된 값을 사용합니다.
이것은 비망록이라고 불린다.

필기화를 통해 해결하다

필기화란 한 번 실시된 계산 결과를 기억하고 다시 불려왔을 때 결과를 돌려주는 것이다.
설치가 매우 간단하다.
fibo2.php

<?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

호출 횟수가 대폭 개선되다.
기록이 없는 상태에서 언제 가치를 돌려받을 수 있을지 모르기 때문에 크게 개량했다.

총결산

귀속 함수를 사용하여 실시할 때 중복 호출로 인한 성능 악화를 고려하여 기록 등을 통해 성능에 미치는 영향을 억제할 수 있다.
뭐, 이번만큼은 보통 순환을 빨리 하는 편이지만 그래도 회귀 함수를 사용하고 싶다면 기억해 주셨으면 좋겠습니다.
이번에는 이렇게.

참고 자료

안정적인 위키백과