Рекурсия в NASM: Фибоначчи - PullRequest
Новая
       24

Рекурсия в NASM: Фибоначчи

0 голосов
/ 21 ноября 2018

Мне трудно получить рекурсию на работу.Ну, рекурсия для себя!Факториальный калькулятор не был таким сложным, мне потребовалось около полдня, чтобы понять это. 

   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,когда он умножает их все. Easy peasy

Но теперь, когда мне нужно вызвать функцию с (n-1) И (n-2), я не могу себе представить, как это будет работать, так как я долженуправлять адресами возврата, стеком, значениями.Все, что я знаю, это то, что каждый раз, когда вычитается 1 или 2, а результат равен 1, он должен включать счетчик, который затем даст нам результат.

, поэтому возвращайте с n-1, пока n-1 =1, в этом случае вернуть n-2, а затем снова n-1.Я просто , так что растерялся и боролся за это уже 2 дня.

Спасибо за помощь, спасибо!

1 Ответ

0 голосов
/ 21 ноября 2018

Это тот же принцип.В факториальном случае вы временно сохраняете 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
...