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

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

PHP对尾递归没有优化效果

先来看下实验。

01

<?php

02	function factorial($n)

03

{

04	if($n == 0) {

05

return 1;

06

}

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

08

}

09

10	var_dump(factorial(100));

11

?>

如果安装了XDebug的话，可能会遇到如下错误：

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

这是XDebug的一个保护机制，可以通过max_nesting_level选项来设置。放开设置的话，程序还是能够正常运行的。

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

1	Fatal error:  Allowed memory size of … bytes exhausted

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

01

<?php

02	function factorial($n, $acc)

03

{

04	if($n == 0) {

05	return $acc;

06

}

07	return factorial($n-1, $acc * $n);

08

}

09

10

11	var_dump(factorial(100, 1));

12

?>

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

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

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

PHP如何消除递归

先看看下面的源代码：

01

<?php

02	function factorial($n, $accumulator = 1) {

03	if ($n == 0) {

04	return $accumulator;

05

}

06

07	return function() use($n, $accumulator) {

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

09

};

10

}

11

12	function trampoline($callback, $params) {

13	$result = call_user_func_array($callback, $params);

14

15	while (is_callable($result)) {

16	$result = $result();

17

}

18

19	return $result;

20

}

21

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

23

24

?>

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

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

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

小结

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

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