问题陈述：
Fibonacci为1200年代的欧洲数学家，在他的著作中曾经提到：若有一只兔子每个月生一只小兔子，一个月后小兔子也开始生产。起始只有一只兔子，一个月后就有两只兔子，二个月后有三只兔子，三个月后有五只兔子(小兔投入生产)......。这就是Fibonacci数列，一般习惯称之为费氏数列，例如如下: 1 1 2 3 5 8 13 21 34 55 89.....
问题解法：
根据问题陈述，我们可以将费氏数列定义为一下：
F(n) = F(n-1) + F(n-2) if n > 1
F(n) = 1 if n = 0, 1
Fibonacci有两种最常见的解法，即迭代法和递归法。
代码详解：
1
/*
2
注：fibanacci数列下标从0开始
3
fibRecurse(int n) 递归计算数列下标为n的值
4
fibIterate(int n) 迭代计算数列下标为n的值
5
*/
6
#include <stdio.h>
7
#include <stdlib.h>
8
9
int
fibRecurse(
int
n);
10
int
fibIterate(
int
n);
11
12
int
main()
13
{
14
int
i, n;
15
printf(
"
Please input a number :
"
);
16
scanf(
"
%d
"
, &
n);
17
printf(
"
Recursion:\n
"
);
18
for
(i=
0
; i<n; i++
) {
19
printf(
"
%-5d
"
,fibRecurse(i));
20
if
((i+
1
)%
10
==
0
) {
21
printf(
"
\n
"
);
22
}
23
}
24
printf(
"
\n
"
);
25
printf(
"
Iteration:\n
"
);
26
for
(i=
0
; i<n; i++
) {
27
printf(
"
%-5d
"
,fibIterate(i));
28
if
((i+
1
)%
10
==
0
) {
29
printf(
"
\n
"
);
30
}
31
}
32
return
0
;
33
}
34
35
int
fibRecurse(
int
n) {
36
if
(n <
0
) {
37
return
-
1
;
38
}
39
if
(n==
0
|| n==
1
) {
40
return
1
;
41
}
else
{
42
return
fibRecurse(n-
1
) + fibRecurse(n-
2
);
43
}
44
}
45
46
int
fibIterate(
int
n) {
47
int
a =
1
, b =
1
, i, s;
48
if
(n <
0
) {
49
return
-
1
;
50
}
51
if
(n==
0
|| n==
1
) {
52
return
1
;
53
}
else
{
54
for
(i=
1
; i<n; i++
) {
55
s = a+
b;
56
a =
b;
57
b =
s;
58
}
59
}
60
return
s;
61
}
