斐波那契数列递归算法,08《算法入门教程》递归算法之斐波那契数列

斐波那契数列递归算法,08《算法入门教程》递归算法之斐波那契数列详细介绍

本文目录一览： 斐波那契数列算法

斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

我们以求解f(10)作为例子来分析递归求解的过程。要求得f(10)，需要求得f(9)和f(8)。同样，要求得f(9)，要先求得f(8)和f(7)……我们用树形结构来表示这种依赖关系

在这棵树中有很多结点会重复的，而且重复的结点数会随着n的增大而急剧增加。这意味这计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的，时间复杂度约等于O(2^n)

空间复杂度分析

在方法一的基础上改进

其实改进的方法并不复杂。上述方法之所以慢是因为重复的计算太多，只要避免重复计算就行了。比如我们可以把已经得到的数列中间项保存起来，如果下次需要计算的时候我们先查找一下，如果前面已经计算过了就不用再次计算了。算法步骤如下

一目了然，O(1) 约等于O(1)

这个是我目前见过最流弊的方式，但是前提你得先会用公式
时间复杂度是O(logn)，就问你流弊不流弊。在介绍这种方法之前，先介绍一个数学公式：

递归法求斐波那契数列的关键语句

递归法求斐波那契数列的关键语句是plaintextCopy codefib（n）=fib（n-1）+fib（n-2）。
斐波那契数列可以用递归的方法求解，其中关键的递归语句是计算第n个斐波那契数的语句。其中，fib（n）表示第n个斐波那契数，fib（n-1）表示第n-1个斐波那契数，fib（n-2）表示第n-2个斐波那契数。
通过递归调用自身，可以不断地计算出前面的斐波那契数，直到计算到初始的斐波那契数1和2。需要注意的是，在实际编写代码时，还需要考虑边界条件和递归终止条件，以及可能的优化措施，以避免重复计算和提高效率。
斐波那契数列的作用
1、数学研究：斐波那契数列在数学领域具有一些特殊的性质和规律，如黄金比例、递归关系等。它们被广泛研究和应用于数论、代数、几何等数学分支中。
2、自然科学：斐波那契数列在自然界中出现的频率较高，如植物的叶子排列、花瓣数目、果实的种子排列等。通过研究和应用斐波那契数列，可以深入理解自然界中的规律和现象。
3、金融和经济学：斐波那契数列在金融和经济学中有着广泛的应用。它们可以用于分析金融市场的走势、价格波动和周期性，以及经济学中的增长模式和周期性。
4、计算机科学：斐波那契数列在计算机科学中有着广泛的应用，如算法设计、动态规划、递归函数等。它们可以用于解决一些实际问题，如编程中的数列求和、排列组合、图形生成等。
5、艺术和设计：斐波那契数列的黄金比例和美学特点被广泛应用于艺术、设计和建筑等领域。它们可以用于创造美感和平衡感的艺术作品、建筑设计和图形构图等。

08《算法入门教程》递归算法之斐波那契数列

本节内容是递归算法系列之一：斐波那契数列递归求解，主要介绍了斐波那契数列的定义，然后用递归的实现思想分析了一下斐波那契数列，最后给出了基于 Java 代码应用递归思想实现斐波那契数列的代码实现及简单讲解。
斐波那契数列（Fibonacci sequence），也称之为黄金分割数列，由意大利数学家列昂纳多?斐波那契（Leonardo Fibonacci）提出。斐波那契数列指的是这样的一个数列：1、1、2、3、5、8、13、21、34、……，这个数列从第 3 项开始，每一项都等于前面两项之和。在数学上，斐波那契数列可以被递推的方法定义如下：
斐波那契数列是数学上面一个经典的例子，并且在日常生活中有很多应用，他还与黄金分割有着密不可分的联系，而且当 n 趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割值 0.618。
在这一节中，我们就需要利用递归的思想去求解斐波那契数列，当给出一个斐波那契中第几项的数字，然后求解出对应的斐波那契数值。在之前，我们已经定义了递归算法的相关概念，并且明确了需要应用递归时候的三要素：
接下来，我们将利用递归的知识来解决斐波那契数列问题，明确在斐波那契数列求解问题中的递归三要素分别是什么。
例如，当我们求解斐波那契数列中的 F (5) 时，按照定义，我们有：
在说明斐波那契数列的递归描述之后，我们看看如何用 Java 代码来实现对斐波那契数列的计算。
运行结果如下：
代码中的第 4 行至第 8 行分别调用斐波那契数列计算函数，计算出斐波那契数列中对应 n=1,2,3,4,5 时斐波那契数列的取值，进行结果比较，判断斐波那契数列程序实现是否正确。代码中的第 12 行至第 20 行是斐波那契数列应用递归方法进行斐波那契数列的计算，按照递归的三要素进行计算处理。
本节主要介绍了用递归思想求解斐波那契数列，在学完本节课程之后，我们了解到了什么是斐波那契数列，并且将递归算法在斐波那契数列中进行了实际应用，需要掌握斐波那契数列的递归求解方法，并自己可以实现相关的代码实现，并清楚里面的每一步逻辑。

尾递归优化的斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。如： 1 1 2 3 5 8 .. 计算公式： F(N) = F(N - 1) + F(N - 2) (N > 1)
尾递归：尾调用的一种特殊情况，特别的是尾递归在最后一步 调用自身 。
我们经常使用诸如递归之类的方法来查找阶乘等，但递归容易发生 堆栈溢出 的问题。
尾递归优点：由于只存在 一个调用栈 ，所以永远不会出现“栈溢出”错误，节省内存。
非尾递归Fibonacci序列实现如下：
尾递归优化的Fibonacci序列实现如下：
小小斐波那契数列常常被面试官偏爱，那接下来有时间会整理一下斐波那契数列算法优化问题~

求解斐波那契数列的时间复杂度，分别用递归和非递归方法

Fibonacci数列
无穷数列1,1,2,3,5,8,13,21,34,55，···，称为Fibonacci数列。它可以递归的定义为
1 n=0
F(n)= 1 n=1
F(n-1)+F(n-2) n>1
第n个Fibonacci数可递归地计算如下：
int Fibonacci ( intn)
{
If(n<=1)return 1;
ReturnFibonacci(n-1)+Fibonacci(n-2);
}
1+T(n-1)+T(n-2) n>1
Tn=
0 n<=1
时间复杂度为指数时间O(kn)
非递归计算如下：
Int Fibonacci(int n)
{
If(n<2)return 1;
else{
int a=b=1;
for(int i=0;i
<n+2;i++)
{

b=a+b;

a=b-a;

return a+b;

}

}

}

时间复杂度为O(n).
</n+2;i++)

用递归法计算斐波那契数列的第n项

#include

int Fibonacci(int n)

{

if( n == 1 || n == 2) // 递归结束的条件，求前两项

return 1;

else

return Fibonacci(n-1)+Fibonacci(n-2); // 如果是求其它项，先要求出它前面两项，然后做和。

}

int main()

{

int n;

printf("please input n: ");

scanf("%d",&n);

printf("Result: %d\n",Fibonacci(n));

return 0;

}

用递归方法计算斐波那契数列的第n项的代码如下：

#include

int Fibonacci(int n)

{

if( n == 1 || n == 2) // 递归结束的条件，求前两项

return 1;

else

return Fibonacci(n-1)+Fibonacci(n-2); // 如果是求其它项，先要求出它前面两项，然后做和。

}

int main()

{

int n;

printf("please input n: ");

scanf("%d",&n);

printf("Result: %d\n",Fibonacci(n));

return 0;

}

扩展资料一【非递归方式计算斐波那契数列第N项】#include

using namespace std;

int Fib(int n)

{

if(n==1 || n==2)

return 1;

int fib1=1;

int fib2=1;

int fib;

for(int i=3; i<=n; ++i)

{

fib = fib1 + fib2;

fib2 = fib1;

fib1 = fib;

}

return fib;

}

void main()

{

int n;

cout<<"input n:>";

cin>>n;

cout<
<fib(n)<<endl;
}

扩展资料二【斐波那契数列的起源】

由于斐波纳挈数列是以兔子的繁殖引入的数学问题，因此也叫“兔子数列”，指的是这样一个数列：0，1，1，2，3，5，8，13...... 从这组数可以很明显看出这样一个规律：从第三个数开始，后边一个数一定是在其之前两个数的和。

在数学上，斐波纳挈数列可以以这样的公式表示：F(0) = 0，F(1) = 1 ，F(n) = F(n-1) + F(n-2),(n>=2)
</fib(n)<

［数据结构与算法分析］斐波那契数列递归算法时间复杂度为多少？

答案应该是2的n次方，当n为3时，调用五次，n为4调用九次
B
附加：当使用{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1，求解释，会将时间复杂度减为A
long fab(long n){ if (n < 2) return 1; return fab(n - 1) + fab(n - 2);}简单推断一下，当n>2时，递归调用的次数call_fab(n) = 2*fab(n) - 1，再简单证明一下。
用call_fab(n)代表递归调用的次数
n = 3时，调用fab(3)，会递归调用fab(1)和fab(2)，而fab(1)和fab(2)只需要调用一次，加上本身一次，一共调用3次，而fab(3) = 2，3 = 2 * 2 - 1，满足推断
n = 4时，fab(4) = fab(3) + fab(2)，所以call_fab(4) = 1 + call_fab(3) + call_fab(2) = 5
fab(4) = 3，满足5 = 3 * 2 - 1
同理n=5也可以简单计算得出，这样我有连续3个结果，作为归纳法证明的基础
假设n = k（k >= 5）成立，即
fab(k) = fab(k-2) + fab(k - 1)，有call_fab(k) = 2fab(k) - 1
那么当n=k+1时，fab(k+1) = fab(k - 1) + fab(k)，
call_fab(k+1) = 1 + call_fab(k - 1) + call_fab(k) = 1 + 2fab(k-1) - 1 + 2fab(k) - 1
= 2(fab(k-1) + fab(k)) - 1 = 2fab(k+1) - 1，归纳法得证。
所以，对于大于2的整数n，其斐波那契数列递归算法的调用次数为2*n的斐波那契数列值 - 1，故答案是D，时间复杂度和该数列是一致的。

递归和非递归算法求解Fibonacci数列

对于Fibonacci数列

我们可以采用递归以及非递归的方法对其进行求解。

下面分别用两种方法求解，并分析算法的时间复杂度。

输入 时，

输入 时，

假设 时 ， 正确,

当 时， 正确。

So the correctness of Algorithm has been proved.

对于 来说，每个问题被分成了两个子问题。每分割一次，问题的规模线性减少。

对于每个节点来说，每个节点对应算法执行一次操作的时间复杂度为 。

二叉树的总层数为 , 所以我们可以近似认为

下面给出具体分析：

对于 :

尾部常数 4 代表 四次常数操作 (1 comparison, 2 subtractions, 1 addition)

我们可以发现 , 代入得：

所以lower bound我们说，

我们认为 ， 因为

可得：

我们可以发现 , 代入得：

所以对upper bound我们说，

综上，该算法时间复杂度

首先，为A[0], A[1]赋值分别需要两个 的操作。

对于循环部分，时间复杂度为 。

所以

综上，迭代方法求解Fibonacci的时间复杂度为

最初发布在我的 个人博客 上。欢迎访问。

用递归函数求斐波那契数列的第n项的值

#include

int fib(int n){if(n<3)return 1; return fib(n-1)+fib(n-2);}int main(){int n; scanf("%d",&n); printf("%d\n",fib(n)); return 0;}

#include

int Fibonacci(int n)

{

if( n == 1 || n == 2) // 递归结束的条件，求前两项

return 1;

else

return Fibonacci(n-1)+Fibonacci(n-2); // 如果是求其它项，先要求出它前面两项，然后做和。

}

int main()

{

int n;

printf("please input n: ");

scanf("%d",&n);

printf("Result: %d\n",Fibonacci(n));

return 0;

}

在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。

扩展资料：

一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当n趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割0.618（或者说后一项与前一项的比值小数部分越来越逼近0.618）。

从第二项开始，每个偶数项的平方都比前后两项之积少1，每个奇数项的平方都比前后两项之积多1。

如：第二项1的平方比它的前一项1和它的后一项2的积2少1，第三项2的平方比它的前一项1和它的后一项3的积3多1。

注：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶，比如从数列第二项1开始数，第4项5是奇数，但它是偶数项，如果认为5是奇数项，那就误解题意，怎么都说不通。

参考资料来源：百度百科--斐波那契数列