【web 开发基础】PHP 中的递归函数 (38)

前言

什么是递归？

递归做为一种算法在程序设计语言中广泛应用。所谓的递归简单地概括就是程序调用自身的编程技巧称为递归（ recursion）。递归在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。我们常见的编程语言中，绝大多数编程语言基本都支持函数的自调用，在这些编程语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言中习惯用递归来实现循环。在支持自调用的编程语言中，递归可以通过简单的函数调用来完成。尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言可以被优化为循环指令。因此，在这些语言中尾部递归不会占用调用堆栈空间。

PHP中的递归函数

递归函数即自调用函数，在函数体内部直接或间接的自己调用自己，即函数的嵌套调用时函数本身。通常在此类型的函数体之中会附加一个条件判断语句，以判断是否需要执行递归调用，并且在特定的条件下终止函数的递归调用动作，把目前流程的主控权交回上一层函数执行。因此当某个执行递归调用的函数没有附加条件判断语句时，可能会造成无限循环的错误情形，也就是我们常说的死循环的情况。

函数递归调用最大的好处在于可以精简程序中的繁杂重复的调用程序，并且能以这种特殊性来执行一些较为复杂的运算动作。比如：列表，动态树状菜单（例如我们常说的无限分类）以及遍历文件目录等操作。相应的非递归函数虽然效率高，但却比较难编程，而且相对来说可读性稍差一些，现代程序设计的目的主要是可读性好，毕竟都是团队协作开发，甚至跨团队协作开发，可读性显然很重要，随着计算机硬件性能的不断提高，程序在更多的场合优先考虑可读而不是高效，所以鼓励用递归函数实现程序思想，当然，我们一般都是平衡两者，也不至于只在乎可读性，而是可读性的占比变高了。

比如汉诺塔问题，斐波那契数列列等是常见可用递归解决的问题，当然这些也有非递归的解法，只是相对来说稍微复杂一点。

编程实践

下面我们通过斐波那契数列的例子简单了解递归函数的声明及使用：

斐波那契数列：1 1 2 3 5 8 13 21 34 55 …前两个值都为1，该数列从第三位开始，每一位都是当前位前两位的和；公式为：Fn = F(n-1) + F(n+1)，代码如下：

<?php
//使用递归方式求斐波那契数
function fb($n){  
  if( $n <=2){
    return 1;
  }else{
    return fb($n-1) + fb($n-2);
  }
}

echo fb(8);

执行结果：

开始时，它是外层调用内层，内层调用更内一层，直到最内层由于条件不成立必须结束，最内层结束了，程序执行就会回到稍外一层继续执行，稍外一层再结束时，退到再稍外一层继续执行，层层退出，直到最外层结束。

接着我们通过非递归的实现来对比两种实现方式的区别：

<?php
function fb($n){  
  if( $n <=2){
    return 1;
  }
  $t1 = 1;$t2 = 1;
  for($i=3;$i<$n;$i++){
    $temp = $t1;
    $t1 = $t2;
    $t2 = $temp + $t2;
  }
  return $t1 + $t2;
}

echo fb(8);

两种方式的结果肯定是一样的，但是从代码量来看，非递归的方式稍微复杂一点，但是可能非递归的方式执行效率更高一些。执行效率对比：时间或许受运行环境影响，每次运行可能不一样，但是应该差不太多