Since Multiplication is simple repetitive addition, if y
is pair, you can divide it by two, and multiply x
by two. (so, 2*2 = 2+2. 2*3 = 2+2+2, 2*4 = 2+2+2+2 ....)
If y
is odd, you can subtract 1, to get a y
that is pair, and you need to add an x
, (basically, 1*y).
Here's a breakdown:
RecMultiply(5,5) :
+- z = RecMultiply(5,2)
| return 5 + 2 * z (=20 +5 =25)
|
|
+-- RecMultiply(5,2) :
+- z = RecMultiply(5,1)
| return 2 * z (=10)
|
+-- RecMultiply(5,1) :
+- z = RecMultiply(5,0)
| return 5 + 0
|
+---RecMultiply(5,0) :
return 0
RecMultiply(5,4) :
+- z = RecMultiply(5,2)
| return 2 * z (=)
|
+-- RecMultiply(5,2) :
+- z = RecMultiply(5,1)
| return 2 * z (=10)
|
+-- RecMultiply(5,1) :
+- z = RecMultiply(5,0)
| return 5 + 0
|
+---RecMultiply(5,0) :
return 0
So, basically, after the recursive bit (that takes care of all the pair multiplications), you might need to add another y
, which in the first case above, is 5
for the first call).
Note the special case of y=1
, which means x*1
which obviously is 5
in our case. Same logic applies.
You might want to look at it like this, if it helps:
static int RecMultiply(int x, int y)
{
switch (y)
{
case 0:
return 0;
break;
case 1:
return x;
break;
default:
return (y%2 ==0) ? RecMultiply(x, y/2)
: x + RecMultiply(x, y/2);
break;
}
}
I think it denotes the +1 (or odd cases) in a more understandable manner.