PHP 实现递归函数算法

递归函数算法在编程时经常会用到,例如循环遍历目录文件结构,循环处理文件数据等。本文介绍使用 PHP 实现递归函数算法的三种方式,分别是利用引用做参数、全局变量、静态变量,来实现递归函数算法。

递归函数最基本的特点是函数自身调用自身,但必须在调用自身前有条件判断,否则无限无限调用下去。理解其原理需要一定的基础知识,包括对全局变量,引用,静态变量的理解,也需对他们的作用范围有所理解。递归函数也是解决无限级分类的一个很好地技巧。如果对无限级分类感兴趣,请参照下文的 PHP 利用递归函数实现无限级分类。

一、利用引用做参数


首先需要理解引用是什么?引用是指两个不同名的变量指向同一块存储地址。简单的说每个变量有各自的存储地址,赋值删除各行其道。现在两个变量共享一块存储地址。例如:$a=&$b;实际上指的是$a不管不顾自己原来的存储地址,非要和$b共享一地址。因而任何对存储地址数值的改变都会影响两个值。

用引用作为参数,成为一个桥梁,形成两个函数间的数据共享。虽然两个函数貌似操作的是不同变量,但是实际上操作的是一块儿内存地址。

例如下面函数:

  1. function test($a = 0, &$result = array())
  2. {
  3. $a ++;
  4. if ($a < 10) {
  5. $result[] = $a;
  6. test($a, $result);
  7. }
  8. echo $a . ',';
  9. return $result;
  10. }
  11. print_r(test());

上面的例子以$a < 10作为判断条件,条件成立,则把$a赋给$result[],将$result的引用传入函数,会将每一次递归产生的$a添加到结果数组$result[]。因而本例生成的$result数组是:

  1. Array
  2. (
  3. [0] => 1
  4. [1] => 2
  5. [2] => 3
  6. [3] => 4
  7. [4] => 5
  8. [5] => 6
  9. [6] => 7
  10. [7] => 8
  11. [8] => 9
  12. )

例子中输出$a的值是:

  1. 10,9,8,7,6,5,4,3,2,1,

相信很多人认为是1,2,3,4,5,6,7,8,9,10,,其实是10,9,8,7,6,5,4,3,2,1,这是为什么呢?

因为函数还没执行输出$a前就进行了下一次的函数递归。当真正执行echo $a是当$a < 10条件不满足的时候,echo $a返回$result,执行完递归函数,开始执行本层的echo $a依次类推。

二、利用全局变量


利用全局变量完成递归函数,首先要理解什么是全局变量?

global在函数内申明变量不过是外部变量的同名引用。变量的作用范围仍然在本函数范围内。改变这些变量的值,外部同名变量的值自然也改变了。但一旦用了&,同名变量不再是同名引用。利用全局变量实现递归函数没必要理解到这么深的一层,还保持原有对全局变量的看法就可以顺理成章理解递归函数。

例如下面函数:

  1. function test($a = 0, $result = array())
  2. {
  3. global $result;
  4. $a ++;
  5. if ($a < 10) {
  6. $result[] = $a;
  7. test($a, $result);
  8. }
  9. echo $a . ',';
  10. return $result;
  11. }
  12. print_r(test());

本例输出内容与上面例子输出内容相同。

三、利用静态变量


什么是静态变量?

静态变量的类型关键字是static,使用关键词static声明的变量就是静态变量,在第一次调用函数的时候对静态变量进行初始化,并且保留变量值。

静态变量例子:

  1. function test()
  2. {
  3. static $count = 0;
  4. echo $count;
  5. $count ++;
  6. }
  7. test(); // 调用 1 次
  8. test(); // 调用 2 次
  9. test(); // 调用 3 次
  10. test(); // 调用 4 次
  11. test(); // 调用 5 次

本例输出01234,并不是00000,原因是第一次调用函数时声明$count变量为静态变量,并赋值0,此后每次调用函数不再声明变量赋值,忽略static $count = 0;这段代码。

静态变量应用到递归函数:

  1. function test($a = 0)
  2. {
  3. static $result = array();
  4. $a ++;
  5. if ($a < 10) {
  6. $result[] = $a;
  7. test($a);
  8. }
  9. echo $a . ',';
  10. return $result;
  11. }
  12. print_r(test());

本例输出内容与上面例子输出内容相同。

四、总结

所谓递归函数,重点是如何处理函数调用自身是如何保证所需要的结果得以在函数间合理“传递”。

最后给大家分享一个 PHP 实现递归与无限分类的方法,具体实现方法如下:

  1. echo "<pre>";
  2. $area = array(
  3. array('id'=>1, 'area'=>'北京', 'pid'=>0),
  4. array('id'=>2, 'area'=>'广西', 'pid'=>0),
  5. array('id'=>3, 'area'=>'广东', 'pid'=>0),
  6. array('id'=>4, 'area'=>'福建', 'pid'=>0),
  7. array('id'=>11, 'area'=>'朝阳区', 'pid'=>1),
  8. array('id'=>12, 'area'=>'海淀区', 'pid'=>1),
  9. array('id'=>21, 'area'=>'南宁市', 'pid'=>2),
  10. array('id'=>45, 'area'=>'福州市', 'pid'=>4),
  11. array('id'=>113, 'area'=>'亚运村', 'pid'=>11),
  12. array('id'=>115, 'area'=>'奥运村', 'pid'=>11),
  13. array('id'=>234, 'area'=>'武鸣县', 'pid'=>21)
  14. );
  15. function t($arr, $pid = 0, $lev = 0)
  16. {
  17. static $list = array();
  18. foreach ($arr as $v) {
  19. if ($v['pid'] == $pid) {
  20. // 这里输出,是为了看效果
  21. echo str_repeat("&emsp;", $lev) . $v['area'] . "<br />";
  22. $list[] = $v;
  23. t($arr, $v['id'], $lev + 1);
  24. }
  25. }
  26. return $list;
  27. }
  28. $list = t($area);
  29. echo "<hr >";
  30. print_r($list);
  31. echo "</pre>";

函数t()内部echo输出效果:

  1. 北京
  2. 朝阳区
  3. 亚运村
  4. 奥运村
  5. 海淀区
  6. 广西
  7. 南宁市
  8. 武鸣县
  9. 广东
  10. 福建
  11. 福州市

print_r($list);输出效果:

  1. Array
  2. (
  3. [0] => Array
  4. (
  5. [id] => 1
  6. [area] => 北京
  7. [pid] => 0
  8. )
  9. [1] => Array
  10. (
  11. [id] => 11
  12. [area] => 朝阳区
  13. [pid] => 1
  14. )
  15. [2] => Array
  16. (
  17. [id] => 113
  18. [area] => 亚运村
  19. [pid] => 11
  20. )
  21. [3] => Array
  22. (
  23. [id] => 115
  24. [area] => 奥运村
  25. [pid] => 11
  26. )
  27. [4] => Array
  28. (
  29. [id] => 12
  30. [area] => 海淀区
  31. [pid] => 1
  32. )
  33. [5] => Array
  34. (
  35. [id] => 2
  36. [area] => 广西
  37. [pid] => 0
  38. )
  39. [6] => Array
  40. (
  41. [id] => 21
  42. [area] => 南宁市
  43. [pid] => 2
  44. )
  45. [7] => Array
  46. (
  47. [id] => 234
  48. [area] => 武鸣县
  49. [pid] => 21
  50. )
  51. [8] => Array
  52. (
  53. [id] => 3
  54. [area] => 广东
  55. [pid] => 0
  56. )
  57. [9] => Array
  58. (
  59. [id] => 4
  60. [area] => 福建
  61. [pid] => 0
  62. )
  63. [10] => Array
  64. (
  65. [id] => 45
  66. [area] => 福州市
  67. [pid] => 4
  68. )
  69. )

(完)