PHP 마스터 | 재귀 이해-PHP 튜토리얼-php.cn

PHP Master | Understanding Recursion

코어 포인트

재귀는 기능을 직접 또는 간접적으로 호출하는 기능을 포함하는 문제 해결 방법입니다 (함수 통화 루프를 통해). 나무와 목록을 반복하거나 대부분의 O (n log n) 종류를 수행 할 때 특히 유용합니다.

재귀 함수에는 기본 사례 또는 보호 조항이 있어야하여 무한히 자신을 호출하지 못하므로 스택 오버 플로우 오류가 발생합니다. 이 기본 예는 특정 조건이 충족 될 때 기능이 추가 재귀 호출을 막는 조건입니다.

재귀의 두 가지 유형이 있습니다 : 직접 재귀와 간접 재귀. 직접 재귀는 함수가 직접 호출되는 반면 간접 재귀는 기능이 다른 함수를 통해 간접적으로 자체 호출됨을 의미합니다. 이 기사는 직접 재귀에 중점을 둡니다.

재귀는 강력한 도구가 될 수 있지만주의해서 사용해야합니다. PHP는 재귀 함수를 최적화하지 않으며, 일반적으로 반복적 인 대응 자만큼 효율적이고 빠르지 않습니다. 그러나 파일 시스템에서 불확실한 깊이를 검색하거나 가로 지르는 등 일부 경우 재귀는 더 효율적 일 수 있습니다.

이전 게시물에서 나는 반복자와 사용 방법에 대해 썼습니다. 오늘, 나는 반복적 인 형제 자매 : 재귀를보고 싶습니다. 그러나 재귀에 대해 논의하기 전에이 코드를 살펴 보겠습니다.

공장은 숫자가 해당 숫자보다 작은 모든 양수를 곱한 결과입니다. 이제 다음과 같이이 예를 다시 작성해 봅시다 :

우리 가이 두 기능을 호출 할 때, 우리는 동일한 결과를 얻지 만 두 번째 함수는 스스로 호출하여 Factorior를 계산합니다. 이것을 재귀라고합니다.

재귀 란 무엇입니까?

재귀 함수는 직접 또는 함수 호출 루프를 통해 자신을 호출하는 함수를 나타냅니다. 재귀는 또한 먼저 더 작은 버전의 문제를 해결 한 다음 해당 결과를 사용하여 다른 계산을 추가하여 원래 질문에 대한 답을 형성하는 문제 해결 방법을 참조 할 수 있습니다. 일반적으로 작은 버전을 해결하는 과정 에서이 접근 방식은 "기본 예제"에 도달 할 때까지 작은 버전의 퍼즐 등을 해결합니다. 재귀 함수를 작성하려면 리턴 메소드를 제공해야합니다. 그렇지 않으면 전화 스택이 버스트, 스크립트가 시작되거나 메모리가 소진 될 때까지 계속 호출합니다. 이를 보호 조항 또는 기본 사례라고합니다. 재귀 함수의 가장 간단한 형태는 다음과 같습니다.

재귀 유형

함수가 직접 호출되면 직접 재귀라고합니다. 함수 호출 루프에서 함수의 최종 호출을 간접 재귀라고합니다. 간접 재귀의 다음 예를 확인하십시오 :

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

로그인 후 복사

위의 예는 실제로 쓸모없는 코드이며, 다른 함수를 통해 함수가 간접적으로 호출되는 방식을 보여주기 만하면됩니다. a (n & gt; 4) 또는 b (n & gt; 4)를 호출하면 다른 함수 호출에서 호출 된 함수가 발생합니다. 기능은 이와 같이 간접적으로 스스로를 부를 수 있음을 아는 것이 중요하지만,이 기사에서는 직접 재귀 만 다루고 있습니다.

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

로그인 후 복사

<🎜 🎜> <<> 실용적인 예

<🎜 🎜> 재귀의 힘을 보여주기 위해 배열에서 키를 검색하는 함수를 작성하고 결과를 반환합니다.

모든 것이 순조롭게 진행되었지만 배열의 두 번째 레이어에만 반복되었으므로 세 번째 층에서 "Fibonacci"를 검색하는 데 실패했습니다. 우리가 불확실한 깊이의 배열을 검색한다면 충분하지 않을 것입니다. 우리는 검색을 재귀 함수로 다시 쓸 수 있습니다 :

재귀 함수를 사용하여 하드 코딩 된 함수의 깊이가 없기 때문에 깊은 배열의 여러 레이어를 검색 할 수 있습니다. 배열의 모든 값을 반복 할 때까지 계속 실행됩니다.

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

로그인 후 복사

<🎜 🎜> <<> 헤드 재귀 및 꼬리 재귀 <🎜 🎜>

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

로그인 후 복사

지금까지 우리의 모든 예에서, 우리는 소위 헤더 재귀를 사용하고 있습니다. 함수가 자체 호출되면 자체 값을 반환하기 전에 통화 결과를 기다립니다. 반환 값에서 작동하지 않지만 필요한 모든 값을 매개 변수로 전달하는 함수를 작성할 수 있습니다. 이것을 꼬리 호출 (또는 꼬리 재귀)이라고합니다. 언어의 런타임이 때때로 통화를 최적화 할 수 있기 때문에이 방법은 일반적으로 선호됩니다. 따라서 통화 스택을 폭파 할 위험이 없지만 PHP는 그렇지 않습니다. 다음은 테일 호출을 위해 수정 된 우리의 계승 예입니다. 재귀 호출의 결과는 더 이상 조작하기보다는 반환됩니다.

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

로그인 후 복사

일반적인 제안

반복적으로 쓸 수있는 모든 코드는 재귀 적으로 작성할 수 있습니다. 그러나 이것은 항상 쉬운 것은 아닙니다 (현명한). 재귀는 나무와 목록을 통해 반복하거나 대부분의 O (n log n) 종류를 수행 할 때 우수합니다. 파일 시스템 검색과 같은 반복적 인 문제를 나누어야 할 때 재귀는 반복적 인 방법보다 더 적합하며 검색을 위해 하위 디렉토리로 이동해야합니다. 재귀는 불확실한 깊이를 가로 질러 잘 작동합니다. PHP는 재귀 함수를 최적화하지 않으며, 테일 호출을 위해 작성하더라도 재귀 함수는 위의 코드 예에서와 같이 때때로 작업을 더 잘 수행하지만 반복적 인 상대보다 비효율적이고 느립니다. 재귀는 일반적으로 기능 프로그래밍에서 반복에 선호되는 대안이므로 대부분의 기능 언어는 재귀 기능을 최적화합니다. XDEBUG를 사용하는 경우 시스템 구성을 확인하십시오. 기본적으로 100 번의 재귀 통화를 제한 하며이 한계를 초과하면 스크립트가 "최대 중첩 제한에 도달했습니다"오류에 도달했습니다. 이 설정을 변경 해야하는 경우 Debug.max_nesting_level 구성 값을 업데이트 할 수 있습니다. 마지막으로, 스택 힙과 재귀에 대한 설명을 읽고 스택 오버플로가 재귀 중에 스택을 호출하는 일을 이해하게하는 것이 가장 좋습니다.

결론 이 기사에서는 재귀와 반복과의 비교를 광범위하게 소개합니다. 또한 재귀 기능을 작성하는 방법, 언제 작성 해야하는지, 그리고 그 이유를 보여주었습니다. 또한 재귀를 사용할 때 발생할 수있는 함정에 대해 경고하려고합니다. 재귀는 이와 같습니다. 많은 숙련 된 프로그래머조차도 몇 년 동안 그것을 사용하지 않을 수도 있으며, 많은 사람들이 그것을 들어 본 적이 없으며, 이는 진정으로 강력한 개념이기 때문에 부끄러운 일입니다. 이 게시물을 통해 자신의 재귀 기능을 작성하기에 충분한 지식을 제공 할 수 있기를 바랍니다. 그러나 화재를 사용하는 것처럼 항상이 도구를주의해서 사용해야합니다.

flickr

의 Alexandre Duret-Lutz의 사진 PHP (FAQ)의 재귀 이해에 대한 FAQS (FAQ)

PHP 재귀 함수의 기초 예는 무엇입니까? PHP 재귀 함수의 기본 예는 함수가 무한대로 호출되는 것을 방지하는 조건입니다. 재귀 기능의 핵심 부분입니다. 기본 케이스가 없으면 재귀 함수는 자체를 무한대로 호출하여 스택 오버플로 오류가 발생합니다. PHP에서 기본 예제는 일반적으로 함수의 시작 부분에서 "if"문을 사용하여 정의됩니다. 이 함수는 재귀 호출을 진행하기 전에이 조건을 확인합니다. 조건이 충족되면 함수는 값을 반환하고 스스로 호출을 중지합니다. PHP의 재귀 기능은 어떻게 작동합니까?

PHP의 재귀 함수는 기본 케이스라는 특정 조건이 충족 될 때까지 자체 기능 본문에서 자체를 호출합니다. 재귀 함수가 호출되면 특정 작업을 수행 한 다음 스스로 호출하여 작업을 반복합니다. 이 프로세스는 기본 케이스가 충족 될 때까지 계속되고 함수는 자체 호출이 중지됩니다. 함수가 호출 될 때마다 호출 스택에 새 레이어가 생성되어 변수를 저장하고 함수 호출의 주소를 반환합니다. 기본 케이스가 충족되면 함수가 돌아 오기 시작하고 레이어별로 통화 스택 레이어를 풀기 시작합니다.

재귀를 사용하여 PHP의 모든 문제를 해결할 수 있습니까? 재귀는 PHP에서 강력한 도구가 될 수 있지만 재귀를 사용하여 모든 문제를 해결할 수있는 것은 아닙니다. 재귀는 파일 디렉토리를 가로 지르거나 정렬 배열과 같은 더 작고 유사한 문제로 나눌 수있는 문제에 가장 적합합니다. 그러나 부적절하게 사용되면 재귀로 인해 메모리 사용량이 높고 오버플로 오류가 발생할 수 있습니다. 또한 기능 호출의 오버 헤드로 인해 일반적으로 반복 솔루션보다 느립니다. 따라서 당면한 문제를 이해하고 올바른 접근법을 선택하는 것이 매우 중요합니다. PHP 재귀 함수의 스택 오버 플로우를 방지하는 방법은 무엇입니까?

재귀 함수의 스택 오버 플로우는 함수가 결국 도달 할 기본 인스턴스를주의 깊게 정의하여 방지 할 수 있습니다. 기본 케이스는 조건이며,이 조건이 충족되면 기능은 추가 재귀 호출을 중지합니다. 기본 케이스가 없으면 함수는 자체를 무한히 호출하여 스택 오버플로를 유발합니다. 또한 각 재귀 호출이 무한 재귀를 피하기 위해 기본 케이스에 더 가깝게 함수를 제공하는 것이 중요합니다.