目录
1. fibnacci数列
2. fibnacci数列的递归表达式
F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
3. C语言
由于递归算法的特性，当计算较大的Fibonacci数列,如Fib(100)、Fib(1000)和尤其是Fib(10000)，递归方法会变得极其低效，因为它会产生大量的重复计算，导致指数级的时间复杂度，使计算时间非常长甚至超过计算机的可接受范围。所以一分钟内计算出Fib(10000)是不太可能的。
4. 用GDB查看递归的堆栈情况
点击查看代码
$ gdb ./fibonacci
(gdb) break fibonacci
Breakpoint 1 at 0x1123: file fibonacci.c, line 4.
(gdb) run
Starting program: /path/to/fibonacci
Breakpoint 1, fibonacci (n=10) at fibonacci.c:4
4 if (n <= 1) {
(gdb) bt
#0 fibonacci (n=10) at fibonacci.c:4
#1 0x00005555555551e9 in fibonacci (n=9) at fibonacci.c:8
#2 0x0000555555555217 in fibonacci (n=10) at fibonacci.c:9
#3 0x000055555555526a in main () at fibonacci.c:18
(gdb) frame 1
#1 0x00005555555551e9 in fibonacci (n=9) at fibonacci.c:8
8 return fibonacci(n-1) + fibonacci(n-2);
(gdb) info locals
n = 9
(gdb) continue
Continuing.
Breakpoint 1, fibonacci (n=9) at fibonacci.c:4
4 if (n <= 1) {
(gdb) bt
#0 fibonacci (n=9) at fibonacci.c:4
#1 0x00005555555551e9 in fibonacci (n=8) at fibonacci.c:8
#2 0x0000555555555217 in fibonacci (n=9) at fibonacci.c:9
#3 0x000055555555526a in main () at fibonacci.c:18
(gdb) frame 1
#1 0x00005555555551e9 in fibonacci (n=8) at fibonacci.c:8
8 return fibonacci(n-1) + fibonacci(n-2);
(gdb) info locals
n = 8
(gdb) continue
...