;《Windows汇编语言程序设计教程》p170习题7：
;用递归子程序显示Fibonacci数列，Fibonacci数列Fn定义为:F0=0,F1=1,F2=1,Fn=Fn-2+Fn-3(n>=3)。
;2006-12-15 高玉涵
;程序不考虑处理负数与溢出。
.386
.model flat,stdcall
option casemap:none
includelib /masm32/lib/msvcrt.lib
printf PROTO C :dword, :vararg
scanf PROTO C :dword, :vararg
.data
dVar dword 6
szMsg1 byte '请输入一个大于2的整数:', 0
szMsg3 byte 'F%d = %d', 0ah, 0
szMsg4 byte 'ebx=%d', 0ah, 0
szInputFmt byte '%d', 0
.code
Fibonacci proc C n:dword
local dret:dword ;存放子程序的返回值。
local dvar:dword ;存放n值(中间计算)。
cmp n, 2
jle exitrecurse ;n<=2
push n
pop dvar ;dvar=n
dec dvar ;n-1
invoke Fibonacci, dvar ;Fibonacci(n-1)
mov dret, eax ;保存上次调用的返回值。
dec dvar ;相当于n-2
invoke Fibonacci, dvar ;Fibonacci(n-2)
add eax, dret ;eax子程序返回值,eax=n-1+n-2。
ret
exitrecurse:
mov eax, 1 ;保存子程序返回值。
ret
Fibonacci endp
start proc
invoke printf, offset szMsg1 ;提示。
invoke scanf, offset szInputFmt, offset dVar ;获取用户输入的值。
cmp dVar, 2
jle exitrecurse ;dVar<=2,退出。
mov ecx, dVar
lop:
push ecx ;保存ecx值。
invoke Fibonacci, ecx
invoke printf, offset szMsg3, ecx, eax
pop ecx ;还原ecx值。
loop lop
exitrecurse:
ret
start endp
end start
程序运行结果：
请输入一个大于2的整数:7
F7 = 13
F6 = 8
F5 = 5
F4 = 3
F3 = 2
F2 = 1
F1 = 1
注：
程序中有一个陷阱：它使用递归步骤计算Fibonacci(n-1)和Fibonacci(n-2),但是，在计算Fibonacci(n-1)时也将计算Fibonacci(n-2),这个额外的计算代价有多大呢？
答案是：它的代价远远不止一个冗余计算：每个递归调用都触发另外两个递归调用，而这两个调用的任何一个还将触发两个递归调用，再接下去的调用也是如此。这样，冗余计算数量增长得非常快。例如：在递归计算Fibonacci(10)时,Fibonacci(3)的值被计算了21次。但是，在递归计算Fibonacci(30)时，Fibonacci(3)的值被计算了317,811次。当然，这317,811次计算所产生的结果是完全一样的，除了其中之一外，其余的纯属浪费。这个额外的开销真是相当恐怖！