백엔드 개발 PHP 튜토리얼 PHP与Recursion_PHP教程

PHP与Recursion_PHP教程

Jul 13, 2016 pm 05:52 PM
php 그리고 사용 할 수 있다 합리적인 존재하다 흔한 개념 ~의 프로그램 작성 재귀

在程序设计中,递归(Recursion)是一个很常见的概念,合理使用递归,可以提升代码的可读性,但同时也可能会带来一些问题。

下面以阶乘(Factorial)为例来说明一下递归的用法,实现语言是PHP:

function factorial($n) {
    if ($n == 0) {
        return 1;
    }

    return factorial($n - 1) * $n;
}

var_dump(factorial(100));

?>
如果安装了XDebug的话,可能会遇到如下错误:

Fatal error: Maximum function nesting level of ’100′ reached, aborting!

注:这是XDebug的一个保护机制,可以通过max_nesting_level选项来设置。

即便代码能正常运行,只要我们不断增大参数,程序迟早会报错:

Fatal error:  Allowed memory size of … bytes exhausted

为什么呢?简单点说就是递归造成了栈溢出。有几个方法可以用来规避这个问题,比如说利用尾调用(Tail Call)来消除递归对栈的影响。

下面以Lua作为描述语言来说明尾调用的含义,代码如下:

function factorial(n)
    if (n == 0) then
        return 1
    end

    return factorial(n - 1) * n
end

print(factorial(100))
这段代码同样会遇到栈溢出的问题。怎样利用尾调用来搞定呢?让我们先来看看尾调用的定义:如果一个函数在执行了一次函数调用后,不再做别的事就称为尾调用。形象点说就是直接返回一个函数调用。尾调用不会返回原来的函数,所以不需要额外的栈保留调用函数的数据。上面代码改成尾调用后类似下面代码的样子:

function factorial(n, accumulator)
    accumulator = accumulator or 1

    if (n == 0) then
        return accumulator
    end

    return factorial(n - 1, accumulator * n)
end

print(factorial(100))
注:关于Lua中尾调用的介绍可以参考:Proper Tail Recursion。

照猫画虎,我们用PHP来实现一个尾调用版本的阶乘:

function factorial($n, $accumulator = 1) {
    if ($n == 0) {
        return $accumulator;
    }

    return factorial($n - 1, $accumulator * $n);
}

var_dump(factorial(100));

?>
可惜测试后才发现PHP根本不支持尾调用!好在天无绝人之路,仔细阅读维基百科中关于尾调用的介绍,你会发现里面提到了Trampoline的概念。简单点说就是利用高阶函数消除递归,依照这样的理论基础,我们可以把上面的尾调用代码改写成如下方式:

function factorial($n, $accumulator = 1) {
    if ($n == 0) {
        return $accumulator;
    }

    return function() use($n, $accumulator) {
        return factorial($n - 1, $accumulator * $n);
    };
}

function trampoline($callback, $params) {
    $result = call_user_func_array($callback, $params);

    while (is_callable($result)) {
        $result = $result();
    }

    return $result;
}

var_dump(trampoline('factorial', array(100)));

?>
看上去不错,不过我不得不向大家道个歉,本文用递归实现阶乘其实是个玩笑,实际上只要用一个循环就行了,《代码大全》里专门提到了这一点:

function factorial($n) {
    $result = 1;

    for ($i = 1; $i         $result *= $i;
    }

    return $result;
}

var_dump(factorial(100));

?>
还有很多别的方法可以用来规避递归引起的栈溢出问题,比如说Python中可以通过装饰器和异常来消灭尾调用,让人有一种别有洞天的感觉:

Tail Call Optimization Decorator (Python recipe)
另外,Python之父关于为何不在Python中支持尾调用的博文也很有看头:

Tail Recursion Elimination
Final Words on Tail Calls
好了,就写到这吧。除非能提升代码可读性,否则没有必要使用递归;迫不得已之时,最好考虑使用Tail Call或Trampoline等技术来规避潜在的栈溢出问题。

作者::老王

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/478119.htmlTechArticle在程序设计中,递归(Recursion)是一个很常见的概念,合理使用递归,可以提升代码的可读性,但同时也可能会带来一些问题。 下面以阶乘...
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Dec 24, 2024 pm 04:42 PM

PHP 8.4는 상당한 양의 기능 중단 및 제거를 통해 몇 가지 새로운 기능, 보안 개선 및 성능 개선을 제공합니다. 이 가이드에서는 Ubuntu, Debian 또는 해당 파생 제품에서 PHP 8.4를 설치하거나 PHP 8.4로 업그레이드하는 방법을 설명합니다.

CakePHP 데이터베이스 작업 CakePHP 데이터베이스 작업 Sep 10, 2024 pm 05:25 PM

CakePHP에서 데이터베이스 작업은 매우 쉽습니다. 이번 장에서는 CRUD(생성, 읽기, 업데이트, 삭제) 작업을 이해하겠습니다.

CakePHP 날짜 및 시간 CakePHP 날짜 및 시간 Sep 10, 2024 pm 05:27 PM

cakephp4에서 날짜와 시간을 다루기 위해 사용 가능한 FrozenTime 클래스를 활용하겠습니다.

CakePHP 파일 업로드 CakePHP 파일 업로드 Sep 10, 2024 pm 05:27 PM

파일 업로드 작업을 위해 양식 도우미를 사용할 것입니다. 다음은 파일 업로드의 예입니다.

CakePHP 라우팅 CakePHP 라우팅 Sep 10, 2024 pm 05:25 PM

이번 장에서는 라우팅과 관련된 다음과 같은 주제를 학습하겠습니다.

CakePHP 토론 CakePHP 토론 Sep 10, 2024 pm 05:28 PM

CakePHP는 PHP용 오픈 소스 프레임워크입니다. 이는 애플리케이션을 훨씬 쉽게 개발, 배포 및 유지 관리할 수 있도록 하기 위한 것입니다. CakePHP는 강력하고 이해하기 쉬운 MVC와 유사한 아키텍처를 기반으로 합니다. 모델, 뷰 및 컨트롤러 gu

CakePHP 유효성 검사기 만들기 CakePHP 유효성 검사기 만들기 Sep 10, 2024 pm 05:26 PM

컨트롤러에 다음 두 줄을 추가하면 유효성 검사기를 만들 수 있습니다.

CakePHP 로깅 CakePHP 로깅 Sep 10, 2024 pm 05:26 PM

CakePHP에 로그인하는 것은 매우 쉬운 작업입니다. 한 가지 기능만 사용하면 됩니다. cronjob과 같은 백그라운드 프로세스에 대해 오류, 예외, 사용자 활동, 사용자가 취한 조치를 기록할 수 있습니다. CakePHP에 데이터를 기록하는 것은 쉽습니다. log() 함수는 다음과 같습니다.

See all articles