Problem C
Ninety-One
Let’s say you want to write a function that takes a single parameter $n$ and, if $n$ is greater than 100, returns $n$ minus 10, and 91 otherwise. Besides being a somewhat pointless function, it would also be trivial to implement:
if n > 100 then
return n - 10
else
return 91
end if
It turns out there is recursive function, called the McCarthy 91 function, that behaves the same way but which requires multiple recursive calls to produce the final result. The function is defined thusly:
\[ M(n) = \left\lbrace \begin{array}{l l} n-10 & \text {if }n>100 \\ M(M(n+11)) & \text {if }n\leqslant 100 \end{array}\right. \]Even though this function may seem pointless, its complex recursive pattern makes it a useful test case for programming languages and formal proof systems.
Your solution must use a RECURSIVE function, using the definition presented above.
On the exam, any other type of solution will receive zero points!
EVEN IF KATTIS JUDGES IT AS CORRECT!
Input
The input contains a single positive integer: $n$.
Output
The output is the value of $M(n)$
| Sample Input 1 | Sample Output 1 |
|---|---|
1000 |
990 |
| Sample Input 2 | Sample Output 2 |
|---|---|
20 |
91 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 |
91 |
| Sample Input 4 | Sample Output 4 |
|---|---|
1872681 |
1872671 |
