斐波那契数列

1. 什么是斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……

2. 递归表达式

F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

3. 代码

#include <stdio.h>
#include <stdlib.h>
int fib(int n)
{
if(n<=1)
{
    return 1;
}
else
{
    return fib(n-1)+fib(n-2);
}
}

int main()
{
int n,i;
long long result;
printf("Please input how many times you want the program to run\n");
scanf("%d",&n);
i=1;
while(i<=n)
{
    result=fib(i);
    printf("%lld ",result);
    i++;
}
return 0;
}

下面这部分程序是没有使用递归的

int main()
{
long long f1,f2,f3;
int n,i;

char c;

Restart:;

f1=1,f2=2;

printf("Please input how many times you want the program to run\n");
scanf("%d",&n);
if(n>=3)
{
    printf("%d %d ",f1,f2);
    for(i=1; i<=(n-2); i++)
    {
        f3=f1+f2;
        printf("%lld ",f3);
        f1=f2;
        f2=f3;
    }
}
else
{
    printf("Variable n must be not less than 2");
}

printf("\nRestart?(y/n)\n");
getchar();
scanf("%c",&c);
if(c=='y')
{
    goto Restart;
}

return 0;//我先写的这个，因为不知道什么叫递归，我以为就是循环结构，但是这个程序会有数据溢出，所以问了ai才搞懂什么是递归，应该用上面那个递归的
}

4. 运行结果截图

1. 10次

2. 100次

跑到这四五十次就已经跑不动了，一分多钟也就跑一半吧

查了一下递归算法的时间复杂度

那么循环算法的时间复杂度是O(n)？

5.调试查看堆栈情况

堆栈方面的知识学习参考了娄老师的博客

……cgdb出问题了？好像没有c语言i/oput的文件，在step调试中没法输入

修改一下代码，在固定次数下查看堆栈

没问题了

完成