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

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

 

一：用递归算法打印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

 

十进制整数转二进制字符串的递归写法:

public String dtob(int n) {
if (n == 0 || n == 1) {
return Integer.toString(n);
} else {
return dtob(n / 2) + Integer.toString(n % 2);
}
}
 

递归很简单，但许多人理解不了，其实就是自已调用自己，
首先你要把算法描述成递归，如阶乘 ： n!=n*(n-1)!
就是递归了，要计算 n!就是要计算 n与(n-1)!的乘积，
这(n-1)!就是又调用自已了。递归也要有结束递归的情况，
不能无限制的递归，否则，栈溢出了；
线性递归的效率很低，可以改成循环迭代；