输入n,求斐波那契数列第n项。斐波那契数列的第0项为0，第一项为1，之后的项依次为前两项之和。

思路一：

递归 要求第n项，首先就要求出第n-1,n-2项，依次类推。递归的出口就是第0项为0，第1项为1.使用递归虽然代码很简单，但如果n大一点的话，所产生的运行时开销会非常大，这样做的后果就是效率非常低下。

思路二：

非递归 使用非递归的话，效率会很高。设置两个三个变量分别表示当前值和前两项的值，使用循环求解。（本例中，只使用两个变量表示这些值）

#include<stdio.h> #include<stdlib.h> //递归 int fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; return fib(n - 1) + fib(n - 2); } //非递归 int fib(int n) { int num1 = 0; int num2 = 1; for (int i = 0; i < n; i++) { num1 = num1 + num2; //将num1和num2的后一项的值保存到num1里面 num2 = num1 - num2; //再将num2换成原来num1的值 } return num1; } //test int main() { int n = 0; scanf("%d", &n); int ret = fib(n); printf("%d\n", ret); system("pause"); return 0; }