PHP递归函数

递归函数即自调用函数,也就是函数在函数体内部直接或间接地自己调用自己。需要注意的是使用递归函数时通常会在函数体中附加一个判断条件,以判断是否需要继续执行递归调用,当条件满足时会终止函数的递归调用。

递归函数最大的好处在于可以精简程序中繁杂重复的程序,并且能以这种特性来执行一些较为复杂的运算动作。例如列表、动态树型菜单以及遍历目录等操作。相应的非递归函数虽然效率高,但却比较难编程,而且相对来说可读性差。

递归思想

递归的主要思想就是,把一个相对复杂的问题(原始问题)转化为一个个与原问题相似的规模较小的问题(子问题)来解决,等一个个小问题解决了,最终的大问题自然就解决了。

递归方法只需少量的程序就可描述出解题过程所需要的多次重复计算,大大减少程序的代码量。当然,递归函数也不是完美的,也有一定的缺点,那就是递归方法函数的运行效率不高。

在 PHP 中最大递归层数也不是没有限制的,这与程序的内存限额有关,PHP5 默认允许一个程序使用 128M 的内存,因此当递归层数过大导致 128M 内存耗尽时,程序就会产生一个致命错误并退出。PHP7 默认允许使用 256M 的内存。

PHP 允许使用的最大内存可以通过修改 php.ini 文件来修改,如下所示:

; Maximum amount of memory a script may consume (128MB)
; http://php.net/memory-limit
memory_limit=256M

PHP中的递归

想要实现递归,需满足以下两个条件:
  • 子问题需与原始问题为同样的事,且更为简单。
  • 不能无限制地调用本身,必须有一个出口,化简为非递归状况处理。

【示例】使用递归函数实现 n! 的阶乘。
<?php
    function factorial($num){
        //确定递归函数的出口
        if($num == 1){
            return 1;
        }else{
            return $num*factorial($num - 1);
        }
    }

    echo '15 的阶乘是:'.factorial(15);
?>
运行结果如下:

15 的阶乘是:1307674368000

【示例】计算斐波那契数列。

斐波那契数列数列如下所示:

1、1、2、3、5、8、13、21、34、...

实现代码如下所示:
<?php
    function demo($num){
        //
        if($num == 1 || $num == 2){
            return 1;
        }else{
            return demo($num - 1) + demo($num - 2);
        }
    }

    echo '数列第 10 位是:'.demo(10);
?>
运行结果如下:

数列第 10 位是:55