! Program to print the nth fibonacci number F(n)
! where F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
! using unoptimised recursion.
! Michael Johnson, 2011.
!
!	This program is here to illustrate
!	how recursion can be implemented in machine code.

	.data
n:	.word 30

	.text
start:
	set 0x10000, %r14	! Initialise stack pointer
	set n, %r1
	ld  [%r1], %r1       	! get value of n
	set fib, %r3		
	jmpl %r3, %r15		! Calculate F(n)
	nop
	mov %r4, %r8		! Print F(n)
	ta  4
	mov '\n', %r8  		!   and \n
	ta 1
	ta 0			! Then STOP.

fib:
	! This subrouting calculates F(%r1) and stores it in %r4
	! It trashes register 4
	! It uses, but restores registers 1,5,15

	add %r14, -4, %r14	! Save registers 1, 5 and 15 on stack
	st %r15, [%r14]
	add %r14, -4, %r14	
	st %r5, [%r14]
	add %r14, -4, %r14
	st %r1, [%r14]

	set 0, %r4		! F(0) = 0
	cmp %r1, 0
	be  done
	nop
	set 1, %r4	    	! F(1) = 1
	cmp %r1, 1
	be  done
	nop

	! Now, we know we're not looking for F(0), nor F(1),
	! so let's just use the formula F(n) = F(n-1) + F(n-2)

	dec %r1
	jmpl %r3, %r15
	nop
	mov %r4, %r5		! %r5 = F(n-1)
	dec %r1
	jmpl %r3, %r15
	nop			! %r4 = F(n-2)

	add %r4, %r5, %r4	! F(n) = F(n-1) + F(n-2)


done:
	ld [%sp], %r1		! Restore registers 1, 5 and 15 from the stack
	add %sp, 4, %sp
	ld [%sp], %r5		
	add %sp, 4, %sp
	ld [%sp], %r15
	add %sp, 4, %sp

	jmpl %r15+8, %r0	! Return F(%r1)
	nop