听说你们都不会递归?那来看看这道题吧 #C语言 #计算机 #编程 #程序员

441
28
179
54
举报
发布时间:2024-08-05 08:42
全部评论
大家都在搜:
为什么用递归效率低[疑问]是因为频繁地进行函数调用吗
2年前·广东

2

分享
回复
力扣上用循环可以战胜99%[看]
2年前·辽宁

2

分享
回复
...
这个就是动态规划吧
2年前·广东

1

分享
回复
太厉害了
11月前·安徽

0

分享
回复
啊!没听懂
2年前·云南

0

分享
回复
居然还有打字比我快的……[发呆]
2年前·河北

0

分享
回复
非递归求第n项,不用数组也行,用两个变量保存前项即可。long long fib(int n){ assert(n>0); if(n==1||n==2)return 1; if(n==3)return 2; long long a=1,b=2; for(int i=4;i<n;++i){ long long x=b; b+=a; a=x; } return b;}[握手]
2年前·广西

0

分享
回复
小美递归可以记忆化一下,当递归深度大了,会爆栈。[握手]
2年前·广西

0

分享
回复
你凭什么要求?不就是为了自己讲课吗 好像天下就一种方法似的
2年前·北京

0

分享
回复
2年前·重庆

0

分享
回复
创想IT小美老师讲嵌入式AI
创想IT小美老师讲嵌入式AI

粉丝14.2万获赞50.9万

智能文稿

斐波那契数列的递归与非递归实现(C语言)

一、斐波那契数列的定义

斐波那契数列是一个经典的数学序列,其特征为:前两项均为1,从第三项开始,每一项的值等于前两项之和。数学定义如下:
当 ( n = 1 ) 或 ( n = 2 ) 时,( F(n) = 1 );
当 ( n > 2 ) 时,( F(n) = F(n-1) + F(n-2) )。

二、递归实现方法

1. 实现思路

递归实现的核心是直接利用斐波那契数列的数学定义:

  • 递归出口:当 ( n = 1 ) 或 ( n = 2 ) 时,返回1;
  • 递归规律:当 ( n > 2 ) 时,返回 ( F(n-1) + F(n-2) )。

2. 代码示例

函数名称为 fable,参数为整数 ( n )(表示求第 ( n ) 项),返回值为第 ( n ) 项的斐波那契数值。

int fable(int n) {
    if (n == 1 || n == 2) {  // 递归出口
        return 1;
    } else {  // 递归规律
        return fable(n - 1) + fable(n - 2);
    }
}

3. 特点

  • 优点:代码简洁,逻辑直观,易于快速实现(适合时间紧张、需快速交付的场景);
  • 缺点:效率低,存在大量重复计算(如计算 ( F(5) ) 时需重复计算 ( F(3) )、( F(2) ) 等)。

三、非递归实现方法(数组+动态内存分配)

1. 实现思路

非递归实现通过迭代计算,利用数组存储中间结果,避免重复计算:

  1. 动态申请大小为 ( n ) 的数组(使用 malloc);
  2. 初始化数组前两项为1(对应 ( F(1) ) 和 ( F(2) ));
  3. 从下标2开始迭代计算,每一项等于前两项之和;
  4. 保存结果后释放动态内存(使用 free),避免内存泄漏。

2. 代码示例

#include <stdlib.h>  // 包含malloc和free函数
int fable(int n) {
    int* p = (int*)malloc(n * sizeof(int));  // 动态申请数组空间
    if (p == NULL) {  // 判断内存申请是否成功
        return -1;  // 申请失败返回错误标识
    }
    
    // 初始化前两项
    p[0] = 1;  // F(1)
    p[1] = 1;  // F(2)
    
    // 迭代计算第3项至第n项
    for (int i = 2; i < n; i++) {
        p[i] = p[i - 1] + p[i - 2];
    }
    
    int result = p[n - 1];  // 保存第n项结果(数组下标从0开始,故为p[n-1])
    free(p);  // 释放动态内存
    return result;
}

3. 特点

  • 优点:效率高,无重复计算,时间复杂度为 ( O(n) );
  • 缺点:代码逻辑较递归复杂,需手动管理动态内存(申请与释放)。

四、两种方法的对比与应用场景

实现方式 代码复杂度 执行效率 适用场景
递归 简单 低 快速实现、逻辑验证、时间紧张时
非递归 中等 高 实际应用、对效率要求高的场景

五、总结

斐波那契数列的两种实现方法体现了递归与迭代在编程中的典型应用。递归注重逻辑直观,非递归注重执行效率。实际开发中需根据场景选择:追求快速交付时用递归,追求性能时用非递归。相关C语言知识点(如函数、数组、动态内存管理等)在系统学习中需重点掌握。

热榜推荐