循环实现斐波那契数列or递归函数

解题思路:

注意事项:

参考代码:

方法一：循环（推荐）

#include<stdio.h>

int main()

{

int k;

scanf("%d",&k);

long long n1=1,n2=1;

// 初始化前两项：f1=第1项，f2=第2项

long long nk=0;

// 处理边界情况：k=1或k=2，直接输出1

if(k==1||k==2)

{

    printf("1");

    return 0;

    //若没有return 0;，程序会继续执行后续代码：

    //最终会执行printf("%lld", fk);

    //此时会打印fk的随机垃圾值，导致输出结果错误

}

// 从第3项循环计算到第k项，无重复计算

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

{

    nk=n1+n2;// 当前项 = 前两项之和

    // 更新前两项，为下一次循环做准备

    n1=n2;

    n2=nk;

}

printf("%lld",nk);

return 0;

}

方法二：递归（时间超限）

//递归实现存在大量重复计算，导致效率极低

#include<stdio.h>

// 递归函数：对应斐波那契递归公式

long long fib(int k)

{

    // 1. 递归终止条件 → 对应递归公式的初始条件 F(1)=1、F(2)=1

    if(k==1||k==2)

    {

        return 1;// 最简单的子问题，直接返回结果

    }

    // 2. 递归调用 → 对应递归公式的递推关系 F(k) = F(k-1) + F(k-2)

    // 问题规模缩小：k → k-1、k-2，最终会收敛到终止条件

    return fib(k-1)+fib(k-2);

}

int main()

{

int k;

scanf("%d",&k);

// 调用递归函数并输出结果

printf("%lld",fib(k));

return 0;

}