2025年C语言递归和非递归分别实现求第n个斐波那契数

科技前沿 • 2025-02-17 18:46 • 阅读 51

大家好，我是讯享网，很高兴认识大家。

C语言递归和非递归分别实现求第n个斐波那契数

一、斐波那契额数列是什么？

形如:1 1 2 3 5 8 13 21 34 55 …,后一项总是前两项的和,这种数所组成的数列,就叫斐波那契数列.

二、非递归实现

因为第n个斐波那契数是第n-1和n-2的和,所以我们要先定义三个变量a,b,c用来存放n,n-1,n-2即a=n-2,b=n-1,c=n,c=a+b;然后这三个变量一步一步的向后移动一位,就是a=n-1,b=n,c=n+1,c=a+b,这样就能求第n+1位斐波那契额数,移动示意图如下:
在这里插入图片描述
讯享网
实现整体往后移动一位,将b赋值给a,c赋值给b,c=a+b;不难发现第一项和第二项都为1,所以当n>2时开始循环,如此循环n-2次,即可得到第n位斐波那契额数.

代码实现如下：

#include<stdio.h> int main() { 
    int n = 0; int a = 1; int b = 1; int c = 1; scanf("%d", &n); while (n > 2) { 
    c = a + b; a = b; b = c; n--; } printf("%d\n", c); return 0; }

讯享网

二、递归实现

创建一个Fib函数,int b是用来接收传过来的值,相当于输入的a的值,当b<=2时,就返回1;否则则返回Fib(b - 1)+ Fib(b - 2)进行迭代,逐层迭代,进而求出斐波那契额数,最终总会算到Fib(1)+ Fib( 2),如下图:
在这里插入图片描述
代码实现如下:

讯享网#include<stdio.h> int Fib(int b) { 
    if (b <= 2) { 
    return 1; } else { 
    return Fib(b - 1)+ Fib(b - 2); } } int main() { 
    int a = 0; scanf("%d", &a); int sum=Fib(a); printf("%d\n", sum); return 0; }

总结

递归的实现可能需要思考,但是方便,循环实现更加容易想到.递归会产生很多重复的中间值,递归太深会导致运算时间久,所以具体问题具体分析,适合的才是最好的.恳请大佬们的建议,一起进步学习.

2025年C语言递归和非递归分别实现求第n个斐波那契数

C语言递归和非递归分别实现求第n个斐波那契数

一、斐波那契额数列是什么？

二、非递归实现

二、递归实现

总结

相关推荐