汇编语言递归：结果总是打印零；递归方法中的逻辑问题？

Question

我目前正在参加汇编语言（摩托罗拉 68K 汇编程序）课程。我有一个项目，我的任务是打印斐波那契数的结果，最多为 30。例如，如果用户输入 4，结果应该是 3（因为它是前两个数字的总和).但是，我的主程序（prog4.s）却不断打印出0，请问这个问题和递归方法的逻辑有关系吗？问题出在别处吗？这是我的递归方法代码 (fib.s)

* fib.s
* long fib(int n) {
*     if(n==0) { 
*      return 0;
*     }
*     else if(n==1) {
*      return 1;
*     }
*     return fib(n-1) + fib(n-2);
* }

ORG 00

fib:
    link      A6,#0
    movem.l   D1-D2,-(SP)
    move.w    8(A6),D1
    TST.w     D1
    BNE       next
    BRA       out

next:
    cmpi.w    #1,D1
    BNE       recurse
    add.w     #1,D0
    BRA       out

recurse:
    move.w    D1,D2
    subq.w    #1,D1
    move.w    D1,-(SP)
    JSR       fib
    move.w    D0,D1      * save copy of fib(n-1)

    adda.l    #2,SP

    subq.w    #2,D2
    move.w    D2,-(SP)
    JSR       fib
    add.w     D2,D1
    add.w     D1,D0        * return fib(n-1) + fib(n-2)

    adda.l    #2,SP

out:
    movem.l   (SP)+,D1-D2
    unlk      A6
    rts

    end

这是调用 fib.s

的程序的代码

fib:   EQU   00
start: initIO
setEVT

lineout     title
lineout     prompt
linein      buffer
cvta2       buffer,D1

* Place parameter on the stack and move the stack pointer
move.w      D1,-(SP)

*Jump to the fib subroutine
JSR         fib

*Pop starting parameter off the stack 
adda.l      #2,SP

cvt2a       buffer,#6
stripp      buffer,#6
lea         buffer,A0
adda.l      D0,A0
clr.b       (A0)
lineout     answer

break

prompt:     dc.b 'Enter a number between 1 and 30: ',0
answer:     dc.b 'The Fibonacci number is: '
buffer:     ds.b  80
       end

注意事项：fib.s中注释掉的算法是我需要使用的算法。任何 help/advice 将不胜感激。

Answer 1

你的程序几乎是正确的。
问题不在于递归本身的逻辑，而是你如何 return 每次调用计算的值。
与调试器进行几次跟踪会话将帮助您发现问题。

我先给你提示一下。这些行

add.w     D1,D2      *fib(n-1) + fib(n-2)
add.w     D2,D0      *add fib(n-2)

不要按照评论说的去做。
D2 持有 n-2，D1 持有 fib(n-1) 并且 D0 是 fib(n-2) 所以最终结果是 fib(n-1) + fib(n-2) + n - 2。只需将它们替换为 ADD.W D1, D0 到 return fib(n-1) + fib(n-2)。

还有另外两个错误，但是您 return 其他两种情况的值（n = 0 和 n = 1).

我强烈建议您尝试使用Easy68k自带的68k模拟器自行调试对fib(0)和fib(1)的调用
一个重要的建议：在开始模拟之前将 D0 设置为一个随机值（例如：$55555555）并使用 F7 来跟踪执行。

如果您未能找到其他错误，请看这里

The instruction used to return 1 for the n = 1 case is ADD.W #1, D0 which depends on the previous value of D0.
It should be MOVE.W #1, D0.
If n = 0 the function branches to out without modifying D0, it should set D0 to zero.
Something like MOVE.W #0, D0 or another zeroing idiom.

Answer 2

问题出在调用程序中，prog4.s。您正确读入了值，但将错误的寄存器传递到堆栈。宏 linein 将二进制补码整数存储在 D0 中，而不是 D1 中。由于 D1 在您传入之前其中有零，因此它每次都返回零。调用程序的正确代码应该是这样的：

fib:    EQU             00
start:  initIO                  * Initialize (required for I/O)
        setEVT                  * Error handling routines
*       initF                   * For floating point macros only


lineout         title
lineout         prompt
linein          buffer
cvta2           buffer,D0


* Place parameters on the stack and move the stack pointer
move.w          D0,-(SP)


* Jump to the fib subroutine
JSR             fib


* Pop starting parameters off of the stack
adda.l          #2,SP


cvt2a           buffer,#6
stripp          buffer,#6
lea             buffer,A0
adda.l          D0,A0           * Sets A0 to the address of D0
clr.b           (A0)
lineout         answer


break                           * Terminate execution
*
*----------------------------------------------------------------------
*       Storage declarations


title:  dc.b    'Program #4, Christopher Moussa, cssc0702',0
prompt: dc.b    'Enter a number between 1 and 30: ',0
answer: dc.b    'The Fibonacci number is: '
buffer: ds.b    80
    end

汇编语言递归：结果总是打印零；递归方法中的逻辑问题？

Assembly Language Recursion: Result always printing zero; issue with logic in recursive method?

recursion

assembly

fibonacci

easy68k