Introduction to Computer Architecture Recursion
For this assignment, you will write MIPS assembly language functions to implement three of the
Hofstadter functions. Most of these will require that you write one recursive function. However, the last
one will require you to write a pair of mutually recursive functions. If the parameter is negative, then you
should return -1 for an error condition.
1. Hofstadter G sequence
𝐺(0) = 0
𝐺(𝑛) = 𝑛 − 𝐺(𝐺(𝑛 − 1)), 𝑛 > 0
2. Hofstadter H sequence
𝐻(0) = 0
𝐻(𝑛) = 𝑛 − 𝐻 (𝐻(𝐻(𝑛 − 1))) , 𝑛 > 0
3. Hofstadter Female and Male sequences
𝐹(0) = 1
𝑀(0) = 0
𝐹(𝑛) = 𝑛 −𝑀(𝐹(𝑛 − 1)), 𝑛 > 0
𝑀(𝑛) = 𝑛 − 𝐹(𝑀(𝑛 − 1)), 𝑛 > 0
You should not need to modify the test suite. You only need to write the functions. Since QT SPIM
expects all of your code to be in a single file, you can concatenate them together in a few ways. If you are
on Windows, you can use the included batch file to do the work for you. Simply dragging your source file
and dropping it on the batch file should be sufficient. If you are having trouble with the batch file, make
sure that your file names match those below. You can also use a command line operation.
Windows: copy /Y “
Unix: cat “
Your program should include appropriate comments indicating what the code should be doing and
what registers are being used for. After displaying the results, your program should exit cleanly. You should
test your programs using the SPIM simulator to ensure their functionality before submitting them. You
should only submit your four functions. You will not receive credit if you submit the test suite in any form.
You should also not include any driver or debug code in your submission.
Objectives:
1. To introduce creating recursive functions.
2. To introduce stack manipulation.
3. To review creating and calling simple functions.
4. To review control statements.
5. To review parameter checking.
Introduction to Computer Architecture Recursion
Expected Output:
##———————Testing the Hofstadter G Function———————-##
Test #0 passed: G(0) = 0
Test #1 passed: G(1) = 1
Test #2 passed: G(2) = 1
Test #3 passed: G(3) = 2
Test #4 passed: G(4) = 3
Test #5 passed: G(5) = 3
Test #6 passed: G(6) = 4
Test #7 passed: G(7) = 4
Test #8 passed: G(8) = 5
Test #9 passed: G(9) = 6
Test #10 passed: G(10) = 6
Test #25 passed: G(25) = 16
Test #50 passed: G(50) = 50
Test #-1 passed: G(-1) produces an error.
Test #-59 passed: G(-59) produces an error.
##———————Testing the Hofstadter H Function———————-##
Test #0 passed: H(0) = 0
Test #1 passed: H(1) = 1
Test #2 passed: H(2) = 1
Test #3 passed: H(3) = 2
Test #4 passed: H(4) = 3
Test #5 passed: H(5) = 4
Test #6 passed: H(6) = 4
Test #7 passed: H(7) = 5
Test #8 passed: H(8) = 5
Test #9 passed: H(9) = 6
Test #10 passed: H(10) = 7
Test #25 passed: H(25) = 17
Test #50 passed: H(50) = 34
Test #-1 passed: H(-1) produces an error.
Test #-59 passed: H(-59) produces an error.
##————–Testing the Hofstadter Male and Female Functions————–##
Test #0 passed: F(0) = 1
Test #0 passed: M(0) = 0
Test #1 passed: F(1) = 1
Test #1 passed: M(1) = 0
Test #2 passed: F(2) = 2
Test #2 passed: M(2) = 1
Test #3 passed: F(3) = 2
Test #3 passed: M(3) = 2
Test #4 passed: F(4) = 3
Test #4 passed: M(4) = 2
Test #5 passed: F(5) = 3
Test #5 passed: M(5) = 3
Test #10 passed: F(10) = 6
Test #10 passed: M(10) = 6
Test #25 passed: F(25) = 16
Test #25 passed: M(25) = 16
Test #50 passed: F(50) = 31
Test #50 passed: M(50) = 31
Test #-1 passed: M(-1) produces an error.
Test #-59 passed: M(-59) produces an error.
Test #-1 passed: F(-1) produces an error.
Test #-59 passed: F(-59) produces an error.
##—————————–Testing completed.—————————–##