首页 > 代码库 > 通过小案例简单理解递归算法
通过小案例简单理解递归算法
一:用递归算法打印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." "; 7 } 8 echo "<br/>"; 9 $num++; //递归点:什么时候再次调用当前函数10 if($num <= 9){ //递归出口:什么时候不再调用当前函数11 cf99($num);12 }13 }14 cf99(1);
二:斐波那契数列
斐波那契数列指的是这样一个数列 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);
三:利用递归对数组进行快速排序
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);
通过小案例简单理解递归算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。