A4: Recursion
Last updated
Last updated
If you were thinking of getting through this course without encountering everybody's favorite coding topic, we're sorry to disappoint... By now, you should have a fairly thorough understanding of the stack mechanism and its uses (e.g., local subroutine variables). This assignment will put your stack knowledge and abilities to the test.
A recursive subroutine is a subroutine that calls itself, usually with a modified parameter, until a so-called base case is reached (at which point the fun of properly returning from the depths of your call stack begins).
This assignment requires you to write a recursive subroutine. The subroutine itself will not be long with around 15 instructions in total, however, writing it will be fairly difficult due to its recursive nature. Do not get discouraged if it takes you a few hours to get it working (after all, we're not competing for the best time-per-instruction-written score here and a concise but well-thought-out program is usually better than a rushed and messy one).
Write a program that asks the user for an unsigned 64-bit integer () and then prints the factorial () of that number. The factorial should be calculated using a subroutine.
The subroutine should have the following signature:
As the name suggests, it should calculate the factorial of the given argument and return the result.
Even though it is possible (and likely easier) to implement this subroutine iteratively (as opposed to recursively), iterative solutions will not pass the assignment!
There is an automated test on CodeGrade that indicates whether your solution is likely recursive. Some iterative solutions may also pass this test. Thereby, even though you may pass this test, the TA handling your hand-in will again check for recursiveness and will reject your submission if it calculates the result iteratively.
Your main program should get the needed input from the user, call my_factorial to calculate the result, and finally print the result. The final program output should look like this:
where <n> is the given input and <n!> is the factorial of n.
Write a (pseudocode) specification for a recursive factorial algorithm. You may get your specification checked with a TA if you want to. Alternatively, you may want to again implement the specification in a higher-level language (like Python or C++) first to test for correctness.
Implement your specification in Assembly.
Write the remaining parts of the program.
Technically, this assignment does not introduce any concepts that have not appeared before. However, as you are now working with recursive subroutines, it is essential that you have a strong foundational understanding of the concepts of Stack Frames and Local Variables.