首页 > 代码库 > 通过小案例简单理解递归算法

通过小案例简单理解递归算法

 

一:用递归算法打印99乘法表

 1 <?php 2 header(‘Content-Type:text/html; charset=utf-8‘); 3 echo "<h2>用递归算法打印99乘法表</h2>"; 4 function cf99($num=9){ 5     for($i=1; $i<=$num; ++$i){ 6         echo "$i*$num=".$i*$num."&nbsp;&nbsp;&nbsp;&nbsp;"; 7     } 8     echo "<br/>"; 9     $num++;             //递归点:什么时候再次调用当前函数10     if($num <= 9){      //递归出口:什么时候不再调用当前函数11         cf99($num);12     }13 }14 cf99(1);
View Code

二:斐波那契数列

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
从第二项开始每一项都等于前两项的和,注意项是从0开始的

 1 <?php 2 header(‘Content-Type:text/html; charset=utf-8‘); 3 function f($n){ 4     if($n == 0){ 5         return 0; 6     }elseif($n == 1){ 7         return 1; 8     } 9     return f($n-1) + f($n-2);10 }11 echo f(0);
View Code

 

三:利用递归对数组进行快速排序

 

 1 <?php 2 header(‘Content-Type:text/html; charset=utf-8‘); 3 $array = array(12,9,4,18,7,2,38,34,8,3,41); 4 //递归点:什么时候继续调用当前方法 5 //递归出口:什么时候停止调用当前方法 6 function quickSort($arr){ 7     //递归出口 8     $len = count($arr); 9     if($len <= 1){10         return $arr;11     }12     //分割两个数组,创建两个空数组分别放分割出来大的和小的数13     $big = $small = array();14     //从数组中取出第一个元素作为参考值15     $tag = $arr[0];16     //循环完数组大的放入$big,小的放入$small17     for($i=1; $i<$len; $i++){  //注意$i等于1,因为从第二个数开始和设定的第一个比较18         if($arr[$i] > $tag){19             $big[] = $arr[$i];20         }else{21             $small[] = $arr[$i];22         }23     }24     //递归点,分割到最后一个就接受返回值25     $big_sort = quickSort($big);26     $small_sort = quickSort($small);27     //再进行合并28     return array_merge($small_sort,array($tag),$big_sort);29 }30 $result = quickSort($array);31 var_dump($result);
View Code

 

通过小案例简单理解递归算法