How to prove the outcome of both segment of code are equal

Is it possible to prove using induction? If possible what would be the steps to proof A=B?

Main thing i want to proof is outcome of two segments of code are same.

Below is the code:

Segment A:

int A (int x, int y) {
if (y==0) return x;
return A(y, x % y);
}


Segment B:

int B (int x, int y) {
while (y!=0) {
int t = y;
y = x % y;
x = t;
}
return x;
}

• It' enough to prove that both functions indeed compute $gcd(a,b)$ correctly. And then just deduce that they compute the same function. Each function can be easily proved using induction. Jul 12 '17 at 13:55
• That said, you're looking at the usual recursive/iterative pair. You can show that the N'th iteration of the while-loop corresponds to the N'th call of the recursive function. It's clearly the case for the last iteration (y==0) and it's also the case for every preceding iteration. Jul 12 '17 at 14:47
• Can i prove like for k=n+1 recursion in segment A and k=n+1 iterations in segment B, result of x and y are the same for both segment? Jul 13 '17 at 6:22
• Should convert from image to text to enable searching. Jul 14 '17 at 13:31
• Cross-posted: cs.stackexchange.com/q/77837/755, math.stackexchange.com/q/2357013/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Jul 17 '17 at 6:23

Proof idea: first of all note that the version A is a recursive version of B. Both A and B halts when $y$ is 0, so in both cases computation lasts until $y$ reaches zero. In both versions the return value is $x$. Also note that each recursive call corresponds to a single step in the while loop. So you can prove that after each recursive call and after each step of the while-loop values of $x$ and $y$ are equals. Induction on the number of steps where we assume $x, y > 0$.

Base step: step 1. In the recursive call (version A) $y$ value is passed as an argument and assigned to $x$ (stored in $x$), but new $y$ takes $x\%y$. In other words, ($x_{new} \leftarrow y_{prev}$ and $y_{new} \leftarrow x_{prev} \% y_{prev}$). Similarly, in the version B the following assignments

int t = y;
y = x % y;
x = t;


implies that $x_{new} \leftarrow y_{prev}$ and $y_{new} \leftarrow x_{prev} \% y_{prev}$. So after the first step in both segments new $x$ and new $y$ values are equal.

Induction: assume that after $n$ steps of recursive call and while-loop $x$ and $y$ values are equal. Then by the same argument as in the Base step for step $n+1$ $x_{new}$ and $y_{new}$ in both codes are equal. Thus, when we $y = 0$ both segments return $x$s which are equal.

Alternatively, you could separately prove that both functions compute gcd of two integers $x$ and $y$ and deduce that they must give the same output for same inputs $x$ and $y$. You can do it yourself. Please look here.