C语言实现Fibonacci数列递归

/* 问题描述 Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。 当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。 */ #include<stdio> #include<stdlib> int N=10007; /*计算Fibonacci函数*/ int Fibonacci (int n) { int Fn; if (n==1 || n==2) { Fn=1; } else { Fn = (Fibonacci(n-1) + Fibonacci(n-2))%N; } return (Fn); } int 斐波那契数列（Fibonacci Sequence）是数学中一个经典的数列，它的定义如下：第一项F1和第二项F2都是1，从第三项开始，每一项都等于前两项之和，即Fn = Fn-1 + Fn-2。在给定的C语言代码中，我们看到的是一个用于计算斐波那契数列第n项的递归函数`Fibonacci(int n)`。 递归是一种解决问题的方法，它解决问题的各个部分，直到达到基本情况。在这个例子中，基本情况是当n等于1或2时，函数直接返回1。对于其他n值，函数调用自身来计算Fn-1和Fn-2，然后将它们相加并取模N（这里的N等于10007），以得到Fn的结果。这种递归方法简洁明了，但效率不高，因为它会进行许多重复的计算，尤其是当n较大时。 代码中还包含了一个`main`函数，它提供了一个简单的用户交互界面。用户可以输入一个正整数n，程序会计算并输出斐波那契数列的第n项，并询问用户是否想要继续分析下一个数。通过`while`循环，用户可以选择进行多次分析。如果希望只分析一次，可以简单地删除这个循环。 在实际应用中，由于递归的效率问题，尤其是在大型数值下，通常会使用迭代法或者动态规划来计算斐波那契数列，这两种方法都避免了重复计算，提高了性能。迭代法通过保存上两步的值来避免重复的递归调用，而动态规划则是预先计算并存储所有较小的斐波那契数，以便在需要时快速查表获取。 在C语言中，使用迭代法实现斐波那契数列的一个例子如下： ```c #include<stdio.h> int Fibonacci(int n, int prev1, int prev2) { if (n == 1) return prev1; if (n == 2) return prev2; return (Fibonacci(n - 1, prev2, prev1 + prev2)) % N; } int main() { int n; printf("Enter a positive integer: "); scanf("%d", &n); printf("Fibonacci number is: %d\n", Fibonacci(n, 1, 1)); return 0; } ``` 这里，我们传递了两个额外的参数`prev1`和`prev2`，分别存储前两个斐波那契数，这样在计算新数时，我们只需要一次加法操作，而不需要递归调用。 递归实现的斐波那契数列虽然直观，但效率低下。在C语言中，我们可以利用迭代或动态规划等更高效的方法来解决这个问题。同时，良好的用户交互设计使得程序更易于使用，提供了多次分析的功能。