Recursive FIbonacci arm Assembly-CodePudding

I am trying to convert recursive fibonacci code into arm assembly but I am running into issues. When running my arm assembly, the final value of the sum is 5 when it should be 2. It seems as though my code loops but maybe one too many times. Any help would be much appreciated as I am new to this.

n: .word 3

_start:

    LDR R0, n //n
    MOV R2, #0
    MOV R1, #0
    BL fib
    B end

fib:

    PUSH {R0, R1, LR}
    CMP R0, #0
    BNE test2 //if n>0 go to test2
    //R2 = sum
    ADD R2, #0 //else add 0 to sum
    B rtn
    
test2:

    CMP R0, #1 
    BNE gen // if n> 1 go to gen
    ADD R2, #1 // else add 1 to sum
    B rtn

gen: 

    SUB R0, R0, #1 // n-1
    BL fib 
    MOV R1, R0 //copy fib(n-1) 
    SUB R0, R0, #1 //n-2
    BL fib
    ADD R2, R2, R1 //fib(n-1)   fib(n-2) 

rtn:

    POP {R0, R1, LR}
    BX LR

end:

    B end

CodePudding user response：

This is what your code is doing, and below is a test run. This simply isn't a usual recursive fibonacci.

#include <stdio.h>

void f ( int );

int R2 = 0;

int main () {
    for ( int i = 0; i < 10; i   ) {
        R2 = 0;
        f ( i );
        printf ( "f ( %d ) = %d\n", i, R2 );
    }
}

void f ( int n ) {
    if ( n == 0 ) { R2  = 0; return; }
    if ( n == 1 ) { R2  = 1; return; }
    f ( n-1 );
    f ( n-2 );
    R2  = n-1;
}

f ( 0 ) = 0
f ( 1 ) = 1
f ( 2 ) = 2
f ( 3 ) = 5
f ( 4 ) = 10
f ( 5 ) = 19
f ( 6 ) = 34
f ( 7 ) = 59
f ( 8 ) = 100
f ( 9 ) = 167

Either you started with a broken Fibonacci algorithm, or substantially changed it going to assembly. I don't know how this can be fixed, except by following a working algorithm.

CodePudding user response：

Note that in the C code the only addition is in the fib(n-1) fib(n-2). In particular the special cases just do return 0; and return 1; respectively. Thus your else add 0/1 to sum lines are wrong. You should replace your additions with moves.

Also, you do MOV R1, R0 //copy fib(n-1) which is incorrect because the fib(n-1) has been returned in R2 not R0. That should be MOV R1, R2.

With these changes the code works, even if it is slightly non-standard.