递归优化：斐波那契数列的记忆化求解（C语言）

编写自定义的递归函数，实现求解斐波那契数列。
由用户输入要求解的第n项的编号，n，输出f(n)即第n项的值。 例如F(5)=5

#include <stdio.h>
long long memo[100] = {0};
long long F_mem(int n)
{
if (n <= 0) return -1;
if (n == 1 || n == 2) return 1;

if (memo[n] != 0) return memo[n];

memo[n] = F_mem(n - 1) + F_mem(n - 2);
return memo[n];
}
int main()
{
int n;
printf("请输入第n项：\n");
scanf("%d", &n);

if (n <= 0)
{
printf("n 必须大于 0\n");
return 1;
}

printf("斐波那契数列第%d项：%lld\n", n, F_mem(n));
return 0;
}

这段代码是斐波那契数列计算的优化版本，采用了记忆化递归

什么是记忆化？
记忆化是一种动态规划的实现技巧。它的核心思想是：“如果一个问题已经被解决过，就直接使用之前的结果，不要重复计算。”

• memo数组：充当“笔记本”。memo[n]用来存储第 �n 项斐波那契数的计算结果。
• 初始化：{0}确保所有元素初始为 0。因为斐波那契数列从第 1 项开始都是正整数，所以0可以作为“未计算”的标志。

1. 调用F_mem(n)。
2. 先查表：memo[n]是否有值？
   • 有：直接返回，耗时 �(1)O(1) 。
   • 无：递归计算F_mem(n-1) + F_mem(n-2)，算出后将结果写入memo[n]，然后返回。