# A2: Recursion

{% hint style="info" %}
**CMake target**: `a2`

```bash
cmake --build .build --target a2
```
{% endhint %}

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).

***

## Assignment

Write a program that asks the user for an **unsigned 64-bit** integer ($$n$$) and then prints the factorial ($$n!$$) of that number. The factorial should be calculated using a subroutine.

### Subroutine

The subroutine should have the following signature:

```c
uint64_t my_factorial(uint64_t n)
```

As the name suggests, it should calculate the factorial of the given argument and return the result.

{% hint style="danger" %}
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.
{% endhint %}

### Main Program

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:

```
Enter a number: <n>
<n>! = <n!>
```

where `<n>` is the given input and `<n!>` is the factorial of `n`.

***

## Recommended Approach

1. 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.
2. Implement your specification in Assembly.
3. Write the remaining parts of the program.

***

## Required Knowledge

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](../../../reference-documentation/subroutines/writing-subroutines#stack-frame) and [Local Variables](../../../reference-documentation/subroutines/writing-subroutines#local-variables).
