Every algorithm that use recursion can be computed with iteration, but you can’t understand it before you understand recursion. Recursive functions calls itself again and again. Every recursive algorithm must also has a termination condition. Recursion is a easy for humans to learn, it relies on mathematical induction to make proof safe algorithms. However, recursive algorithms are not very efficient. They make heavy use of stacks which normally resides in RAM or Cache memory. An efficient algorithm makes heavy use of CPU registers and performs very low memory operations.

Following program is an example of recursive factorial algorithm using MIPS assembly language. This program computers factorial of the number entered by the user and prints it. This program also illustrates how to set up procedure stack and how it grows and shrinks. Stack in MIPS can be viewed as an upside down stack. It always grows downward and shrinks upward.

	# Example of function recursion
	# this program computes factorial of entered number with recursion.
	# it illustrates how to set up the procedure stack
	msg_str: 		.asciiz "Enter some Number: "
	.globl main
	la		$a0, msg_str
	li		$v0, 4
	li		$v0, 5
	move		$a0,$v0			# compute 4!
	jal		fac
	move	        $a0,$v0			# get result
	li		$v0,1			# print integer
	li		$v0,10

	# fac(arg) - computes factorial of arg (arg!)
	#	argument is passed in $a0
	#   stack frame:
	#       | ...high address... |
	#       |--------------------|
	#       |                    |
	#       |--------------------|
	#       |  return address    |  +4
	#       |--------------------|  
	#  $sp->|       saved $s0    |  +0
	#       |--------------------|
	#       |  ...low address... |
	# prologue to procedure
	addi            $sp,$sp,-8		# push space for activation frame
	sw		$s0,0($sp)		# save $s0, which we use
	sw		$ra,4($sp)		# save return address
	# start of actual procedure work
	move            $s0,$a0			# get argument ($a0)
	li		$v0,0x00000001	# 1
	beq		$s0,$v0,L2		# end of recursion?
	addi            $a0,$s0,-1		# set up argument (f-1)
	jal		fac			# recursive call 
	mult            $v0,$s0			# multiply
	mflo            $v0			# return mul result
	j		L3			# exit procedure via epilogue
	li		$v0,0x00000001          # return value
	# epilogue to exit procedure
	lw		$ra,4($sp)		# restore $ra
	lw		$s0,0($sp)		# restore $s0
	addi            $sp,$sp,8		# pop activation frame
	jr		$ra				# return

Tagged with: MIPS AssemblySource Code

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.