Note: The purpose of these exercises is to give students experience implementing stacks and recursive procedures in assembly language. 

Finding the factorial of a number:

1. Download the MIPS program p20-1.asm and examine it in your favorite text editor.  This program uses a recursive procedure to calculate the factorial of a non-negative integer.
2. Run the program and observe the stack and how the values get placed on the stack. Also, observe the stack pointer register ($29).

Finding the y^th power of a number x.

1. Download the MIPS program p20-2.asm and examine it in your favorite text editor. The program calculates the y^th power of x (x^y). It uses two procedures "product" and "power". In this program, values that need to be saved for later use are stored in memory.
2. Modify the program so that "register spilling" is accomplished using a stack instead of memory.

Writing a program with recursive procedures.

1. Compute the Nth term in the Fibonacci sequence.

Some challenging recursive algorithms:

Write a MIPS program that uses a recursive procedure to solve one of the problems below. 

1. Use the extended version of Euclid's algorithm to find (signed) integers x and y that satisfy GCD(a,b) = xa + yb for non-negative integers a and b.  Note:  you will need to implement a procedure that returns 3 values.  Since there are only two $v registers, at least one of the values will need to be passed on the stack.  Establish and document your own convention for handling this issue.
2. Use the merge sort algorithm to sort a list of N numbers.