漫谈递归:PHP里的尾递归及其优化

PHP编译器没有对尾递归进行优化
服务器君一共花费了1186.514 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

不同的语言对尾递归的支持都有所不同,编译器的优化也不尽相同。我们之前看了C语言的尾递归,那么在PHP里又是如何的呢?

PHP对尾递归没有优化效果

先来看下实验。

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

为什么呢?简单点说就是递归造成了栈溢出。按照之前的思路,我们可以试下用尾递归来消除递归对栈的影响,提高程序的效率。

<?php
function factorial($n, $acc)
{
    if($n == 0) {
        return $acc;
    }
    return factorial($n-1, $acc * $n);
}


var_dump(factorial(100, 1));
?>

XDebug同样报错,并且程序的执行时间并没有明显变化。

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

事实证明,尾递归在php中是没有任何优化效果的。

PHP如何消除递归

先看看下面的源代码:

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

?>

现在XDebug不再警报效率问题了。

注意到trampoline()函数没?简单点说就是利用高阶函数消除递归。想更进一步了解 call_user_func_array,可以参看这篇文章:PHP函数补完:call_user_func()与call_user_func_array()

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

小结

在C中的尾递归优化是gcc编译器做的。一般的线性递归修改成为尾递归最大的优势在于减少了递归调用栈的开销。从php那个例子就明显看出来递归开销对程序的影响。但是并不是所有语言都支持尾递归的,即使支持尾递归的语言也一般是在编译阶段对尾递归进行优化,比如C语言对尾递归的优化。在使用尾递归对代码进行优化的时候,必须先了解这门语言对尾递归的支持。

在PHP里,除非能提升代码可读性,否则没有必要使用递归;迫不得已之时,最好考虑使用Tail Call或Trampoline等技术来规避潜在的栈溢出问题。

延伸阅读

此文章所在专题列表如下:

  1. 漫谈递归:递归的思想
  2. 漫谈递归:递归需要满足的两个条件
  3. 漫谈递归:字符串回文现象的递归判断
  4. 漫谈递归:二分查找算法的递归实现
  5. 漫谈递归:递归的效率问题
  6. 漫谈递归:递归与循环
  7. 漫谈递归:循环与迭代是一回事吗?
  8. 递归计算过程与迭代计算过程
  9. 漫谈递归:从斐波那契开始了解尾递归
  10. 漫谈递归:尾递归与CPS
  11. 漫谈递归:补充一些Continuation的知识
  12. 漫谈递归:PHP里的尾递归及其优化
  13. 漫谈递归:从汇编看尾递归的优化

本文地址:http://www.nowamagic.net/librarys/veda/detail/2334,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2334

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《敏捷软件开发(原则模式与实践)》 马丁 (作者), 邓辉 (译者)

《敏捷软件开发:原则模式与实践》由享誉全球的软件开发专家和软件工程大师Robert C.Martin将向您展示如何解决软件开发人员、项目经理及软件项目领导们所面临的最棘手的问题。这本综合性、实用性的敏捷开发和极限编程方面的指南,是由敏捷开发的创始人之一所撰写的。1.讲述在预算和实践要求下,软件开发人员和项目经理如何使用敏捷开发完成项目;2.使用真实案例讲解如何用极限编程来设计、测试、重构和结对编程;3.包含了极具价值的可多次使用的C++和JAVA源代码;4.重点讲述了如何使用UML和设计模式解决面向客户系统的问题。

更多计算机宝库...