This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness:
public static int reverse(int n)
{
return reverse(n, 0);
}
public static int reverse(int number, int reverted)
{
if (number!=0)
return reverse(number/10, reverted*10 + number % 10);
else
return reverted;
}
The program requires the integer input to be strictly positive, and the program clearly terminates because n is decreasing. Moreover, we have the relation
reverse(xy, z) = z*reverse(xy) = z*reverse(y)*reverse(x)
How should I proceed to complete a formal proof of correctness for recursion?
z*reverse(y)·reverse(x)
mean? I guess one symbol is multiplication: which one? what is the other one? Isxy
assumed to stand for a 2 digit number, or what, precisely? $\endgroup$ – chi Apr 24 '18 at 12:25reverse(n,0) = 0 * .... = 0
$\endgroup$ – chi Apr 24 '18 at 14:09