CS274: Computer Architecture - Recursion in MIPS

Activity Goals

The goals of this activity are:

1. To properly use recursion and save the stack
2. To diagram a call stack trace for a given program

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

---

Model 1: A Recursive Algorithm

	.data
	prompt: .asciiz "Input an integer x:\n"
	result: .asciiz "Fact(x) = "
	.text
	main:
	# show prompt
	li $v0, 4
	la $a0, prompt
	syscall
	# read x
	li $v0, 5
	syscall
	# function call
	move $a0, $v0
	jal factorial # jump factorial and save position to $ra
	move $t0, $v0 # $t0 = $v0
	# show prompt
	li $v0, 4
	la $a0, result
	syscall
	# print the result
	li $v0, 1 # system call #1 - print int
	move $a0, $t0 # $a0 = $t0
	syscall # execute
	# return 0
	li $v0, 10 # $v0 = 10
	syscall
	.text
	factorial:
	# base case -- still in parent's stack segment
	# adjust stack pointer to store return address and argument
	addi $sp, $sp, -8
	# save $s0 and $ra
	sw $s0, 4($sp)
	sw $ra, 0($sp)
	bne $a0, 0, else
	addi $v0, $zero, 1 # return 1
	j fact_return
	else:
	# backup $a0
	move $s0, $a0
	addi $a0, $a0, -1 # x -= 1
	jal factorial
	# when we get here, we already have Fact(x-1) store in $v0
	multu $s0, $v0 # return x*Fact(x-1)
	mflo $v0
	fact_return:
	lw $s0, 4($sp)
	lw $ra, 0($sp)
	addi $sp, $sp, 8
	jr $ra

view raw MIPSFactorial.s hosted with ❤ by GitHub

Questions

1. Draw a call stack for a call to factorial(3).
2. What registers did factorial save to the stack, and why? In particular, why did it save ra?
3. Remove ra from the stack and re-run this program. What happens, and why?
4. How might one implement the Fibonacci sequence?

---

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.