x64 implementation of the f(n)=f(n-1)+f(n-2) fibonacci algorithm

fib_recur.asm

global fibonacci
extern printf

fibonacci:
  xor rax, rax
  ; f(n = 1|0) = n
  cmp rdi, 1
  jle identity

  ; f(n > 1) = f(n - 1) + f(n - 2)

  ; [rsp] = f(n-1)
  push rdi
  dec rdi
  call fibonacci
  pop rdi

  ; rax = [rsp] + f(n-2)
  push rax
  push rdi
  sub rdi, 2
  call fibonacci
  pop rdi
  add rax, [rsp]
  ; realign stack
  add rsp, 8

  jmp return

identity:
  mov rax, rdi
return:
  ret

I got very stuck on this because I was realigning the stack via sub rsp, 1 which failed because

1. Numbers are 8 bytes, so when I push'd rax, it needed to undo 8 bytes and
2. The stack grows down, so I should have been adding instead of subtracting.

This was so hard. Well, it took less than an hour, but relative to my expectations coming from high level languages, where this is so simple. I should implement this in C (where it is super easy) and see asm output without optimizations - I'm curious how a compiler would do this.

	.file	"fibasm.c"
	.intel_syntax noprefix
	.text
	.globl	f
	.type	f, @function
f:
.LFB0:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	push	rbx
	sub	rsp, 24
	.cfi_offset 3, -24
	mov	DWORD PTR -20[rbp], edi
	cmp	DWORD PTR -20[rbp], 1
	jle	.L2
	mov	eax, DWORD PTR -20[rbp]
	sub	eax, 1
	mov	edi, eax
	call	f
	mov	ebx, eax
	mov	eax, DWORD PTR -20[rbp]
	sub	eax, 2
	mov	edi, eax
	call	f
	add	eax, ebx
	jmp	.L3
.L2:
	mov	eax, DWORD PTR -20[rbp]
.L3:
	add	rsp, 24
	pop	rbx
	pop	rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	f, .-f
	.section	.rodata
.LC0:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB1:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	mov	edi, 20
	call	f
	mov	esi, eax
	lea	rdi, .LC0[rip]
	mov	eax, 0
	call	printf@PLT
	mov	eax, 0
	pop	rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	 1f - 0f
	.long	 4f - 1f
	.long	 5
0:
	.string	 "GNU"
1:
	.align 8
	.long	 0xc0000002
	.long	 3f - 2f
2:
	.long	 0x3
3:
	.align 8
4:

Okay, will study this later