Why doesn't this recursive function work the same way as the other one?

Question

I've been working on a project to write a recursive function in assembly, where it will calculate the Fibonacci number. To start off I made it in Java code:


public class Fibonacci {

    public static int fibonacci(int n) 
    {
        if(n <= 1)
            return n;

        return fibonacci(n-1) + fibonacci(n-2);
    }

This recursive function worked perfectly fine. Although when trying to implement it in assembly code I didn't get the result I expected. After troubleshooting a while, I wrote (roughly) the equivalent code in Java:

    static int n;
    static int rec1; 
    static int result; 

    public static int asmFibonacci(int n) 
    {
        if(n <= 1) {
            result = n;
            return 0;
        }
    
        n = n-1;
        asmFibonacci(n);
        rec1 = result;
    
        n = n-1;
        asmFibonacci(n);

        result = rec1 + result;
        
        return 0;
    
    }

This function gets the same wrong result as the one I had in assembly code, although I still don't understand why, what am I missing? Both functions recur the same amount of times.

Results
asmFibonacci
0 1 1 2 2 3 3 4 4 5
Fibonacci
0 1 1 2 3 5 8 13 21 34

Any help would be much appreciated.

Update

After pushing rec1(R1) onto the stack as well, I got the Fibonacci subroutine in assembly to work as expected.

main

  LDR R0, = 12
  LDR R1, = 0
  LDR R2, = 0
  
  BL Fibonacci

STOP    B STOP
   
Fibonacci
  
   PUSH {LR, R0-R1}
 
   CMP R0, #1
   BLE RETURN

   ADD R0, #-1
   BL Fibonacci
   MOV R1, R2

   ADD R0, #-1
   BL Fibonacci
   
   ADD R0, R1, R2

RETURN   

   MOV R2, R0
   POP {R0-R1, LR}
   BX LR
   
   END

return n seems wrong. I think that should be return result at the bottom — MTilsted, May 01 '21 at 14:02
@MTilsted I'm not using the return value of the function, I'm instead using the variable result to print out the numbers for asmFibonacci. I can make this clearer. — newBeginner, May 01 '21 at 14:10
*After pushing rec1 and rec2 onto the stack as well* - uh, I hope your asm doesn't actual have any `static` variables (`rec1: dd 0` or whatever). Storing and reloading there is not helpful at all, just registers and stack space are all you need or want. Use comments to keep track of what you're using a register (or stack-frame offset) for. Also see my updated answer: note that after the 2nd call returns, you have everything you need to return a value and don't need to do any more saving of stuff, just restore the one thing saved across the last call. — Peter Cordes, May 01 '21 at 15:00
@PeterCordes No, I'm not using static variables, only register in my assembly code. I don't know what other way I could represent that in Java. Yes, with that I could simplify it even further. — newBeginner, May 01 '21 at 15:28
C / Java local vars are equivalent to asm registers / stack space. There's no distinction between stack and registers because the compiler takes care of putting locals somewhere safe *if* they're needed after some later function calls. Otherwise they can just be in call-clobbered (temporary) registers. — Peter Cordes, May 01 '21 at 15:30

Peter Cordes · Accepted Answer · 2021-05-01T15:01:35.533

Proper recursive code won't use static storage; it's not re-entrant therefore not viable for recursion.

"re-entrant" means that it can be called while you're in the middle of another call, e.g. that evaluating Fib(3) while you're in the middle of Fib(5) doesn't mess up any variables that Fib(5) is going to want to re-read later. Such as static int rec1;.

Use only local variables.

In asm, that means stack space or call-preserved registers. (Using call-preserved registers means preserving the caller's value, again on the stack).

Also note that static int n is shadowed by your int n function arg (the way you wrote it in Java at least), so you avoided the bug of trying to use static n! static int rec2 is useless because you don't need to save it across anything.

Also, static int result; is total insanity. Recursive functions return their result, not just produce a side-effect on a global / static var!

In asm, get used to using registers; not everything should get stored and reloaded from static storage with named labels. Even a debug-mode C compiler wouldn't do that (it would use stack space for locals)

Note that naive double-recursive Fibonacci only needs one total int-sized space for saving something across a call. Across the first call, you save n. Across the second call, you need to save the result of the first call, but you're done with n. You can recycle the same call-preserved register for that.

Recursive Fibonacci is total garbage for performance, of course, and only useful as an exercise in recursion. Approximately O(Fib(n)) vs. O(n) performance for simple iterative repeating x += y; SWAP(x,y) or x+=y ; y+=x; See Assembly Language (x86): How to create a loop to calculate Fibonacci sequence for efficient loops.

Why doesn't this recursive function work the same way as the other one?

1 Answers1