斐波拉契数列，即形如0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...，通项公式为An = An-1 + An-2的数列。那么怎么用递归的方式求出指定位置的斐波拉契数呢？
1. 三种求法
下面将介绍三种利用递归求斐波拉契数的方式，为了比较各方式的效率，需要测量运行时间。程序示例使用Python语言，首先编写一个装饰器来测量运行时间。
def time(func):
import time
def wrapper(*args, **kwargs):
start = time.time()
r = func(*args, **kwargs)
end = time.time()
print("---func {:s}--- {:f} seconds---"
.format(func.__name__, end - start)
)
return r
return wrapper
1.1 直接使用通项公式
既然有通项公式，那么就直接粗暴地使用吧
@time
def fib_1(n):
def aux(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return aux(n - 1) + aux(n - 2)
assert n > 0
return aux(n)
此方式每次求aux(n - 1)时，都会利用递归aux(n - 1) = aux(n - 2) + aux(n - 3)，因此，aux(n - 2)被计算了两次，这样时间复杂度会成指数级增长。
1.2 优化通项
既然求第n项时要使用到n - 1以及n - 2项，那么每次递归时直接返回两项就好了，这样就避免了重复计算。
@time
def fib_2(n):
def aux(n):
if n == 1:
return 0,1
else:
second_front, first_front = aux(n - 1)
current = second_front + first_front
return first_front, current
assert n > 0
return aux(n)[1]
aux(n)返回的是第n - 1以及n项。计算aux(n)时，先求出aux(n - 1)，即可得到第n - 2及n - 1项，那么第n项就可以由这两者相加得到，那么aux(n)也就求出来了。
1.3 尾递归
尽管fib_2时间复杂度是线性的，但是递归过程中需要用临时变量存储每次递归地结果，这样会导致栈增长，当n过大时，会导致Stack overflow。因此，需要想一个尾递归的解法。
这种解法的思路与上述两种不同，不直接从通项入手，通项公式是“从后往前”推导，为什么不用更“人性化”的方法，从前往后计算呢？大家手算时不也是这样算的么？
@time
def fib_3(n):
def aux(second, first, n):
if n == 1:
return first
else:
return aux(first, second + first, n - 1)
assert n > 0
return aux(0, 1, n)
从前往后，依次推到第n项就OK了，这种方法跟循环的思路差不多。
2. 运行结果
if __name__ == '__main__':
import sys
n = int(sys.argv[1])
result = set()
assert len(sys.argv) > 2
for func in sys.argv[2:]:
try:
r = eval('%s(%d)'%(func,n))
result.add(r)
except Exception as e:
print(e)
assert len(result) == 1
print(list(result)[0])
用上述程序试着运行一下吧
$ python3 fib.py 40 fib_1 fib_2 fib_3
---func fib_1--- 57.110849 seconds---
---func fib_2--- 0.000029 seconds---
---func fib_3--- 0.000013 seconds---
102334155
看来优化还是有效果的嘛。但是fib_3虽然是尾递归的形式，但python解释器并没有对尾递归做优化
$ python3 fib.py 666 fib_3
---func fib_3--- 0.000601 seconds---
6859356963880484413875401302176431788073214234535725264860437720157972142108894511264898366145528622543082646626140527097739556699078708088
$ python3 fib.py 6666 fib_3
maximum recursion depth exceeded in comparison
Traceback (most recent call last):
File "fib.py", line 62, in <module>
assert len(result) == 1
AssertionError
轻轻松松就爆栈了
3. C语言尾递归优化
既然python不给力，那么就用C来写一下吧。
$ cat fib.c
long fib(long second, long first, int n) {
if (n == 1)
return first;
else
return fib(first, second + first, n - 1);
}
$ gcc -O2 -c -o fib.o fib.c
$ gobjdump -d fib.o
fib.o: file format mach-o-x86-64
Disassembly of section .text:
0000000000000000 <_fib>:
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 83 fa 01 cmp $0x1,%edx
7: 74 64 je 6d <_fib+0x6d>
9: 8d 4a 07 lea 0x7(%rdx),%ecx
c: 44 8d 42 fe lea -0x2(%rdx),%r8d
10: 83 e1 07 and $0x7,%ecx
13: 74 1f je 34 <_fib+0x34>
15: f7 d9 neg %ecx
17: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
1e: 00 00
20: 48 89 f0 mov %rsi,%rax
23: 48 89 fe mov %rdi,%rsi
26: 48 01 c6 add %rax,%rsi
29: ff ca dec %edx
2b: ff c1 inc %ecx
2d: 48 89 c7 mov %rax,%rdi
30: 75 ee jne 20 <_fib+0x20>
32: eb 03 jmp 37 <_fib+0x37>
34: 48 89 f8 mov %rdi,%rax
37: 41 83 f8 07 cmp $0x7,%r8d
3b: 72 30 jb 6d <_fib+0x6d>
3d: b9 01 00 00 00 mov $0x1,%ecx
42: 29 d1 sub %edx,%ecx
44: 66 66 66 2e 0f 1f 84 data16 data16 nopw %cs:0x0(%rax,%rax,1)
4b: 00 00 00 00 00
50: 48 01 f0 add %rsi,%rax
53: 48 01 c6 add %rax,%rsi
56: 48 01 f0 add %rsi,%rax
59: 48 01 c6 add %rax,%rsi
5c: 48 01 f0 add %rsi,%rax
5f: 48 01 c6 add %rax,%rsi
62: 48 01 f0 add %rsi,%rax
65: 48 01 c6 add %rax,%rsi
68: 83 c1 08 add $0x8,%ecx
6b: 75 e3 jne 50 <_fib+0x50>
6d: 48 89 f0 mov %rsi,%rax
70: 5d pop %rbp
71: c3 retq
MD太复杂了，看不懂。lea 0x7(%rdx),%ecx是什么鬼？反正用jmp代替call就是了。
（完）