NASM中的递归:Fibonacci

Question

我很难让递归发挥作用。嗯，一个n的递归！阶乘计算器并没有那么难，我花了大约半天的时间才算出。

mov eax, [input]
call factorialator
jmp quit
;   
factorialator:
cmp eax, 0
je return
push eax
dec eax
call factorialator
;
pop eax
imul ebx, eax
ret
;
return:
mov ebx, 1
ret

现在，这个函数用n=n-1调用自己，每次都推n，直到n=0，它将所有n相乘简易peasy

但现在，我必须用(n-1(AND(n-2(调用函数，我无法想象这会如何工作，因为我必须管理返回地址、堆栈和值。我所知道的是，每当它减去1或2，结果是1时，它应该包含一个计数器，然后它会给我们结果。

所以以n-1返回，直到n-1＝1，在这种情况下返回n-2，然后再次返回n-1。我只是所以很困惑，已经在这上面挣扎了两天了。

感谢你的帮助，谢谢！

Answer 1

这是相同的原理。在阶乘的情况下，您临时保存N，因为以后需要它来乘以fact(N-1)。
在斐波那契级数的情况中，您也暂时保存N(或N-1(，因为稍后需要它来计算N-2，以便可以计算fib(N-2)。

x86实现可能如下所示：

fib:
cmp eax,1       ; Base case?
jbe done        ; Yes => return n
dec eax
push eax        ; Save n-1 on the stack
call fib        ; Calculate fib(n-1)
xchg eax,[esp]  ; Place fib(n-1) on the stack, while retrieving n-1 into eax
dec eax
call fib        ; Calculate fib(n-2)
add eax,[esp]   ; fib(n-2) + fib(n-1)
add esp,4       ; "Undo" the push operation
done:
ret