傻瓜式理解递归之php递归

  写程序这么久了,有时候别人会问道一些算法比如排序啊,递归啊,总是不知道该怎么去说,今天就来整理一下,让更多的人去傻瓜式的理解递归。递归在网络上有很多定义,但有这么一句话听的最多:递归就是自己调用自己!引用百科的一个故事去理解:

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

这样的故事是不是在做很多重复的事情,像这样的情况下就可以使用递归,递归需要几个条件:

1,递归必须 要有边界条件,也就是递归出口(退出递归)

2,递归前进段和递归返回段,也就是最后得到的值

3,当边界条件(递归出口)不满足时,递归前进;当边界条件(递归出口)满足时,递归返回。

举个递归小例子,比如,

张三去和李四借钱,李四说你等一下,我去找王五借给你,

然后李四去找王五借钱,王五说你等一下,我去找赵六借给你,

最后王五找赵六借钱,赵六借给了王五。(这里就是递归出口)

这里有一个规律就是最先执行的最后返回,比如张三去借钱,最后才会把钱给他。

傻瓜式理解递归,就是忘记递归,假设它的子问题已经解决,从上面的例子说就是假设李四已经有钱。

下面说一个场景,斐波纳契数列:1,      1,      2,      3,      5,      8,      13,   21,   34,   55,   89,   144

已知前两项的和,求第三项的和,因为重复用到这个方法,所以用到递归去解:

斐波那契数列的规律是当前项等于前两项的和,得到的公式是f(n)=f(n-1)+f(n-2);这里的n表示第几项,上递归代码:

这里假设子问题已经解决,加入求第10项的值公式为:f(10)=f(9)+f(8)故而出现上面的公式

1
2
3
4
5
6
function f($n){
    if($n==1 || $n==2){
        return 1; // 递归出口,
    }
    return f($n-1)+f($n-2); // 假设子问题已经解决
}

 用迭代的方法求斐波那契数列:

1
2
3
4
5
6
7
8
9
10
11
function f($n){
    $a = 1;
    $b = 1;
     $v = 1;<br>
    for($i=3;$i<=$n;++$i){
        $v = $a+$b;
        $b = $a;
        $a = $v;
    }
    return $v;
}

 大家常遇到的面试问题:一个猴子看一堆桃子,每天,吃了一半,又多吃一个!当到第十天时,只有一个桃子了。问题,有几个桃子?

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

 

1
2
3
4
5
6
7
8
9
/**
 * 递归实现方法
 */
function f($n=1){
    if($n==10){
        return 1; // 递归出口
    }
    return (f($n+1)+1)*2;
}

 

 

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 用迭代的方法
 */
function f($n){
 
    $v = 1; // 设定初始值
    for($i=9;$i>=$n;--$i){
        $v = ($v+1)*2;
    }
    return $v;
}
echo f(1);

 随后会加一些递归的例子,待续,如果写的有什么不清楚的地方,请批判我

 

 

 

 

傻瓜式理解递归之php递归,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。