关于PHP递归的理解

初学递归发现还是很难以理解的,今天就来小结一下。递归在网络上有很多定义,但这么一句话估计很多人都听过:递归就是自己调用自己!就好比小时候我们听过的一个故事一样

从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?“从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?‘从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?……’”

递归可以理解为做很多重复的事情…像这样的情况下就可以使用递归,递归需要几个条件

  1. 递归必须要有边界条件,也就是递归出口(退出递归)
  2. 递归前进段和递归返回段,也就是最后得到的值
  3. 当边界条件(递归出口)不满足时,递归前进;当边界条件(递归出口)满足时,递归返回。

斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列。说是有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月之后的兔子总数为多少?因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。

数列:1、1、2、3、5、8、13、21、34、……,从这个数列我们可以发现一个规律,及第一和第二个数字都是1,之后的数字都是前两个数字之和。以上问题我们要得出每个月兔子的总数就可以依靠此规律进行代码编写

<?php
function countRabbits($month){
    if($month==1||$month==2){
        return 1; //递归出口
    }
    if($month>2){
        return countRabbits($month-1) + countRabbits($month-2);
    }
}
echo countRabbits(6);
?>

初学的朋友可能不太理解,下面我们来分析一下她的运行的流程
===>当$month=1时 countRabbits(1) = 1; 当$month=2时 countRabbits(2) = 1;
===>countRabbits(6)
===>countRabbits(5) + countRabbits(4)
===>countRabbits(4) + countRabbits(3) + countRabbits(3) + countRabbits(2)
===>countRabbits(3) + countRabbits(2) + countRabbits(2)+ countRabbits(1)+ countRabbits(2)+ countRabbits(1) +1
===>countRabbits(2) + countRabbits(1) + 1 + 1 + 1+ 1+ 1 + 1
===>结果为:8

阶乘

<?php
function factorial($n){
    if ($n==1){
        return 1; //递归出口
    }
    if ($n>=2){
        return $n*factorial($n-1);
    }
}
echo factorial(5);

初学的朋友可能不太理解,下面我们来分析一下她的运行的流程
===>当$n=1时 factorial(1) = 1;
===>5*factorial(4)
===>5*4*factorial(3)
===>5*4*3*factorial(2)
===>5*4*3*2*factorial(1)
===>120

猴子吃桃

一个猴子吃一堆桃子,每天吃一半,又多吃一个!当到第十天时,只有一个桃子了。问题,总共有几个桃子?

解析:第十天,只有一个桃子,第九天就是(1+1)*2个桃子,假设子问题已经解决,f(n)=(f(n+1)+1)*2,第一天的桃子等于第二天桃子加1乘以2

<?php
function peach($n){
    if($n==10){
        return 1; //递归出口
    }
    return (peach($n+1)+1)*2;
}
echo peach(1);
?>