粉丝14.2万获赞50.9万
斐波那契数列是一个经典的数学序列,其特征为:前两项均为1,从第三项开始,每一项的值等于前两项之和。数学定义如下:
当 ( n = 1 ) 或 ( n = 2 ) 时,( F(n) = 1 );
当 ( n > 2 ) 时,( F(n) = F(n-1) + F(n-2) )。
递归实现的核心是直接利用斐波那契数列的数学定义:
函数名称为 fable,参数为整数 ( n )(表示求第 ( n ) 项),返回值为第 ( n ) 项的斐波那契数值。
int fable(int n) {
if (n == 1 || n == 2) { // 递归出口
return 1;
} else { // 递归规律
return fable(n - 1) + fable(n - 2);
}
}
非递归实现通过迭代计算,利用数组存储中间结果,避免重复计算:
malloc); free),避免内存泄漏。#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;
}
| 实现方式 | 代码复杂度 | 执行效率 | 适用场景 |
|---|---|---|---|
| 递归 | 简单 | 低 | 快速实现、逻辑验证、时间紧张时 |
| 非递归 | 中等 | 高 | 实际应用、对效率要求高的场景 |
斐波那契数列的两种实现方法体现了递归与迭代在编程中的典型应用。递归注重逻辑直观,非递归注重执行效率。实际开发中需根据场景选择:追求快速交付时用递归,追求性能时用非递归。相关C语言知识点(如函数、数组、动态内存管理等)在系统学习中需重点掌握。
2
2
1
0
0
0
0
0
0
0