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

Question

I am currently enrolled in an assembly language (Motorola 68K Assembler) course. I have a project where I am tasked with printing the result of a Fibonacci number of a number up to 30. For example, if the user were to enter 4, the result should be 3 (since it is the sum of the previous two numbers). However, my main program (prog4.s) continuously prints out 0. Does the problem have anything to do with the logic of the recursive method? Does the problem lie elsewhere? Here is my code of the recursive method (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 $7000

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

Here is my code for the program that calls fib.s

fib:   EQU   $7000
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

Something to note: The algorithm commented out in fib.s is the one I am required to use. Any help/advice would be much appreciated.

Answer 1

Your program is almost correct.
The problem is not within the logic of the recursion it self, it's how you return the values computed by each invocation.
A couple of tracing sessions with the debugger will help you spot the problem.

I'm giving you a hint first. These lines

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

don't do what the comments say.
D2 holds n-2, D1 holds fib(n-1) and D0 is fib(n-2) so the end result is fib(n-1) + fib(n-2) + n - 2. Just replace them with ADD.W D1, D0 to return fib(n-1) + fib(n-2).

There are two other mistakes, yet in how you return the value for the other two cases (n = 0 and n = 1).

I strongly suggest you to try using the 68k simulator that comes with Easy68k to debug a call to fib(0) and fib(1) by yourself.
An important advice: set D0 to a random value (say: $55555555) before starting the simulation and use F7 to trace the execution.

If you fail at finding the other mistakes, here they are

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.