I have a function that does intermediate calculations to a greatest common divisor deal. and here is how its implemented iteratively (see exteuc() function) .
i tried to implement it recursively too, (see exteuc2() function) . feel free to look at it and give me suggestions if i can improve my recursive implementation in any way. even though it works out. i ask because i'm doing c++ programming after a long long time now.
the function takes 2 numbers and 3 arrays of int size 3 each. copyarr just shifts the contents of arrays left by 1. its needed because the array is of size 3 and as i only need 3 values at one time to do calculations on.
int exteuc2(int num1, int num2, int* x, int* y, int* r)
{
int q, tmp;
r[1] = (num1 * x[1]) + (num2 * y[1]);
tmp = r[1];
if (tmp > 0)
{
q = r[0] / r[1];
x[2] = x[0] - (q * x[1]);
y[2] = y[0] - (q * y[1]);
copyarr(x);
copyarr(y);
copyarr(r);
exteuc2(num1, num2, x, y, r);
}
return q;
}
int exteuc(int num1, int num2, int* x, int* y, int* r)
{
int q;
while (( r[1] = (num1 * x[1]) + (num2 * y[1])) != 0)
{
q = r[0] / r[1];
x[2] = x[0] - (q * x[1]);
y[2] = y[0] - (q * y[1]);
copyarr(x);
copyarr(y);
copyarr(r);
}
return q;
}
edit : i thought i'ld add copyarr function.
here
void copyarr(int* p)
{
p[0] = p[1];
p[1] = p[2];
}