Problem B
Dijkstra's Other Algorithm
You’ve probably heard of Dijkstra’s algorithm for finding the shortest path in graphs (if you haven’t, don’t worry, you’ll learn about it in the Masters Program in Computer Science). This exercise isn’t about that algorithm, but about a different algorithm that Dijkstra came up with to compute the Greatest Common Divisor (GCD) of two numbers (i.e., the largest positive integer that divides two numbers with the remainder being zero).
Dijkstra’s Other Algorithm is a simple and elegant variation on Euclid’s classic algorithm for finding the GCD, but it only works if both numbers, $a$ and $b$, are larger than zero (Euclid’s Algorithm doesn’t have that requirement). The GCD is defined recursively like this:
\[ \text {gcd}(a, b) = \left\lbrace \begin{array}{l l} a & \text {if }a=b \\ \text {gcd}(a-b,b) & \text {if }a>b \\ \text {gcd}(a,b-a) & \text {if }a<b \end{array}\right. \]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$ and $b$, separated by a single space. Both integers are strictly greater than zero, and you can assume they can be stored in a 32-bit integer.
Output
The output contains a single integer: the GCD, computed using the method described above.
| Sample Input 1 | Sample Output 1 |
|---|---|
12 15 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 15 |
5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 11 |
1 |
| Sample Input 4 | Sample Output 4 |
|---|---|
84 268 |
4 |
