### LAB 4: Euclid's GCD algorithm, coefficients finding, recursion

Write a program that takes two positive (non-zero) integers a an b as inputs and computes their GCD (greatest common divisor) using Euclid’s algorithm. A description of the algorithm can be found here.
You have to also find integers m and n such that a*m + b*n = GCD(a,b).

Recursion: the idea is to have a recursive function that returns two values:  the m and n, then compute the GCD using them and the formula above. When the call terminates, you have to manipulate the returned m and n to compute the "new" m and n (see GCD slides for details).

HINT: To return two values you have to be a bit creative. You can do one of the following:
• create a new class/struct as a container for two or three numbers
• use two global arrays for m and n and a static counter : each call to the function gets an index location in each array
•  dynamically allocate an array of two integers, store the right values and return the head of the array as a pointer
• store or "concatenate" m,n into a bigger value v= m+ RANGE*n, (assume m,n<RANGE) and return this composed value v.
For this concatenation to work, you need to store m and n as positive values, but they can be negative sometimes; a simple idea is to add on offset (only for the purpose of storage): store m+OFFSET, n+OFFSET into v=m+OFFSET + (n+OFFSET)*RANGE. Further you have to decode v appropriately: get positive values stored, then subtract the offset. Finally OFFSET should cover  the  possible values for m and n; and RANGE>= 2*OFFSET : you can use something like OFFSET=2048 and RANGE=4096