ARM64 — recursive Fibonacci

Start page1 page2 page3 page4 page5 page6 page7 page8 page9 page10

Recursive Fibonacci in pseudo code

function fib(x0) {
  if x0<=1 {
    return 1
  } else {
    var a = fib(x0-1)
    var b = fib(x0-2)
    return b+a
  }
}

The ARM64 assembler program will look a bit like this program.

In ARM64 assembler

Put this in fib.s:

        .text
        .global _start
        .extern _phex
        .extern _exit
_start:

        mov x0,10
        bl fib   /* argument in X0 and result in X0 */

        bl _phex

        bl _exit

fib:    stp fp,lr,[sp, #-16]!
        mov fp,sp
        sub sp,sp,#0x20     /* room for x0 and a */

        /*  bl _phex */    /* if you need a debug print */

        cmp x0,1
        bgt big
        mov x0,#1
        b end

big:    str x0,[fp,-8]      /* save x0 */
        sub x0,x0,1
        bl fib
        str x0,[fp,-16]     /* save a  */
        ldr x0,[fp,-8]

        sub x0,x0,2
        bl fib

        ldr x1,[fp,-16]     /* b is in x0, just add a */
        add x0,x0,x1

end:
        add sp,sp,#0x20
        ldp fp, lr, [sp], #16
        ret

Make and run the program here with lib4.s from before:

as fib.s -o fib.o
as lib4.s -o lib4.o
ld fib.o lib4.o -o fib
./fib

And it prints 0000000000000059 which is a funny looking Fibonacci number. But remember this is in hex, so 5*16+9 is 89 which looks correct. It is 34+55, and so on.

In the fib.s we didn't save any x-registers on the stack with stp — we didn't need to. We had however some values in local variables.

Beware of what convention you want to use:

• The caller must save relevant registers when calling a function, and then restore them.
• The called function must save and restore the registers used.

Both will work, of course.

Start page1 page2 page3 page4 page5 page6 page7 page8 page9 page10

2025-06-16