它是一个递归函数
不卜段懂可以去百度上搜一下旦做
这个你可以看懂吧?
Fib(int n)
{
if(n<=2)
return 1
else
return Fib(n-1)+Fib(n-2)
}
你取 n=4,则return Fib(3)+Fib(2) -->Fib(3)=Fib(2)+Fib(1) -->Fib(2)=1 Fib(1)=1
--> Fib(3) = 2 所以n=4时,型迟誉返回的值就是 3,它就是一种递归的算法,老师也是教你们学习递归用的,斐波那契函数。
首先我们要了解一下什么是递归。
递归法,递归法就是利用上一个或者上几个状态来求取当前状态的值(个人看法)。也可以陆腔说成函数自己调用自己的一种解决问题的策略。因此递归法通常是依托函数来实现的,递归函数总是会有一个出口,我们在解决递归问题时,只需要找出递归的关系式以及递归函数的出口(这两个可以说是递归函数的核心了)。下面我将在这里举求斐波那契值的例子带领着大家具体的实践一下递归法。
很显然递归函数的递推式是:fib(n) = fib(n-1)+fib(n-2)。
递归函数的出口是当n为1时返回1,当n为0时返回0。
最后递归函数的核心代码就可以写出了:
然后总的代码就是:
具体思路如下:
语句 return fib(n-1)+fib(n-2)的意思就是向前求斐波那契值,直到n-1=1,n-2=0
因为只有第1个和第0个斐波那契值是确定的
例:
当n=3时
第一次调用函数fib会执行第三条语句(因为n>1)这样求回返回卜悉腔fib(2)+fib(1)
第二次调用函数时,因为2>1所有型衫会返回fib(1)+fib(0);因为1不大于1,所以调用函数时
会执行第二条语句返回1值。
第三次调用函数,会执行第一和第二条语句,依次返回0和1从而求得fib(2)
fib(3)=fib(2)+fib(1)
fib(2)=fib(1)+fib(0)
即fib(3)=fib(1)+fib(0)+fib(1)=2*fib(1)+fib(0)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)