php递归求斐波那契数列 图文详解递归执行流程

原创 木鱼  2017-06-30 12:28  阅读 748 次

 

话不多说了,直接开干吧。   

以下高能预警,文字过多,每一步的流程都有详细说明。

大家可以直接跳过看图也行!

递归获得斐波那契数列

/**
 * 递归求斐波那契数列第N个数的值
 * @param int $n
 * @return int
 */
function f( $n ){
    if( $n==1 || $n==2 ){
        return 1; // 递归出口,
    }
    return f($n-1)+f($n-2);
}

本篇文章主要是理解递归的,所以斐波那契数列的函数写法就不想详说了,大致说一下吧:

斐波那契数列

1,    1,    2,     3,     5,     8,    13,  21,  34,   55,   89,   144

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

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

  

我们求第5个斐波那契数是多少,调用上面的函数

echo f(5);

小例子

说个小例子方便理解, 递归是先执行的最后返回结果。

也就是说:

张三去找李四借钱,李四也没有钱,李四去找王五借钱,王五刚好也没有钱,然后王五去找赵六借钱,赵六有钱,把钱给王五了,王五拿着钱又给李四了,李四又把钱给张三了。  

等于说,张三先去找李四要的钱,但是却是最后一个拿到钱的。

递归流程


第一次进入函数 f(5),5不等于1和2,遇见调用自己, f(5-1) + f(5-2),此时没有返回。


此时有两个递归在进行,分别是f(4)和f(3)

然后f(4),再次进入函数,4依然不等于1和2,遇见调用自己, f(4-1) + f(4-2),此时依然没有返回

然后 f(3), 再次进入函数,  3依然不等于1和2, 遇见调用自己,  f(3-1) + f(3-2), 此时依然没有返回

然后 f(2), 再次进入函数, 2等于2, 返回1;

和f(2)同时进行的有f(3-2),也就是f(1),进入函数,1等于1,返回1;

第一组递归返回了,f(3-1)+f(3-2),也就是 f(2) + f(1) , 也就是1+1, 值为2;

 

所以f(4-1)的值就求到了。因为f(3-1)+f(3-2)的上一级是f(4-1),f(3-1)+f(3-2)的值是2; 返回给f(4-1),所以此时f(4-1)的值是2;

 

和f(4-1)同时就行递归的还有f(4-2),也就是f(2),f(2)的返回值是1;

也就是f(4-1)+f(4-2) 等于 2+1 等于3;

 

然后f(4-1)+f(4-2)的上一级是 f(5-1),因为f(4-1)+f(4-2)的返回值是3;所以f(5-1)等于3;

到此为止 f(5-1)已经求完了!

  

和f(5-1)同时进行的还有f(5-2)。

f(5-2)也就是f(3),第一次进入函数,不等于1和2,再次进入函数f(3-1)+f(3-2)。

f(3-1)得到返回值1;

f(3-2)得到返回值1;

f(3-1)+f(3-2)等于1+1 等于2;

所以, f(5-2)的值也求出来了, 值为2。

  

所以结果就是 f(5-1)+f(5-2) 等于 3+2;  斐波那契第5个数刚好是5;

 

 

详细执行流程, 注: 里面的是想加的意思。

本文地址:https://www.m5yu.com/php-recursion-course.html
关注我们:请关注一下我们的微信公众号:扫描二维码,公众号:木鱼博客
版权声明:本文为原创文章,版权归 木鱼 所有,欢迎分享本文,转载请保留出处!

发表评论