# Assignment 4 sample solution, bsy.  nov 12, 1998 created.
#
# fab(n):  0 if n = 0 or 1
#	   1 if n = 2
#	   3 fab(n-1) + 2 fab(n-2) + fab(n-3) otherwise
#
# simple recursion used; this is the problem requirement -- no change in
# the algorithm.  efficiency in terms of not using multiply etc matters.
#

		.text
		.globl fab
fab:		subu	$sp, $sp, 16
		sw	$fp, 4($sp)
		addu	$fp, $sp, 16
		sw	$ra, -8($fp)

		bgtu	$a0, 2, fab_rec
					# $a0 is 0, 1, 2, and return values
					# are    0, 0, 1 respectively
		srl	$v0, $a0, 1	# srl gives the desired result.
		b	fab_done
fab_rec:
#		sw	$a0,0($fp)
		subu	$a0,$a0,1	# n-1
		jal	fab		# fab(n-1)
#		lw	$a0,0($fp)
		sll	$v1,$v0,1	# we avoid using the mul instruction
		addu	$v0,$v0,$v1	# by shift and add to get 3*.
		sw	$v0,-4($fp)
		subu	$a0,$a0,1	# n-2
		jal	fab		# fab(n-2)
		sll	$v0,$v0,1	# 2* is just shift left by 1 bit.
		lw	$v1,-4($fp)
#		lw	$a0,0($fp)
		addu	$v1,$v1,$v0
		subu	$a0,$a0,1	# n-3
		sw	$v1,-4($fp)
		jal	fab		# fab(n-3)
		lw	$v1,-4($fp)
		addu	$v0,$v0,$v1

		addu	$a0,$a0,3

fab_done:	lw	$ra, -8($fp)
		lw	$fp, 4($sp)
		addu	$sp, $sp, 16
		jr	$ra