递归和非递归实现——斐波那契数列
斐波那契数列的递归和非递归实现
斐波那契数列：
指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。
递归的原理：
- 每一级的函数调用都有自己的变量。
- 每一级函数调用都会有一次返回。
- 递归函数中，位于递归调用前的语句和各级调用函数具有相同的执行顺序。
- 递归函数中，位于递归调用后的语句和各级调用函数具有相反的执行顺序。
- 虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。
递归的优缺点：
优点
- 实现简单
- 可读性好
缺点
- 递归调用，占用空间大
- 递归太深，容易发生栈溢出
- 可能存在重复计算
递归的要素：
- 找到递归结束条件
- 找出函数的等价关系式
递归实现斐波那契数列：
先看代码：
int fib(int n)//递归函数
{
if (n == 2 ||n == 1)//结束条件
{
return 1;
}
else
{
return fib(n-2) + fib(n - 1);//递归关系式
}
}
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
ret=fib(n);
printf("%d\n",ret);
system("pause");
return 0;
}
图解递归
n=4：
注:
可以看出递归调用占用空间大，且调用次数很多时容易栈溢出！
结果截图
非递归实现斐波那契数列：
先看代码：
int fib(int n)
{
int n1 = 1;
int n2 = 1;
int ret = 0;
if (n <= 2)//n等于1或2时。
{
return 1;
}
for (int i = 3; i <= n; i++)//通过循环计算n>3时。
{
ret = n1 + n2;
n1 = n2;
n2 = ret;
}
return ret;
}
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
ret=fib(n);
printf("%d\n",ret);
system("pause");
return 0;
}
图解递归
注:
非递归求解比较简单，根据题目规律来写出对应逻辑即可！
结果截图