Help with coding class exercise (find the half of a number without dividing)

The teacher explained more or less what we have to do. My question is about the maths part not the coding part.

The exercise is: Create a function that given a positive integer will return the integer part of the half of that integer. If the number is zero or if the number minus one is zero, it returns zero. Otherwise we subtract one twice from the number, we calculate half of that and then add 1 to the result.

(this is worded in a strange way because you can't do x-2 or x minus or plus any number greater than one or use division. You have to use recursion and add one by one. Anyway I don't think that's relevant here)

I don't understand the bolded part. If you subtract two to an even number you get an even number. If you subtract two to an odd number you get an odd number. With 25 you get 25-2 = 23, 23/2 = 11.5, 11.5+1 = 12.5, which is correct. I just don't get why this works or why it is necessary to subtract one. I think it is because it allows you to calculate the half of odd numbers but I don't understand how.

1 Answer

I'm not sure but I think what they are getting at is something like.

function halfit(k){ if (k)=0, return 0; if (k-1) = 0, return 0; otherwise let k= k-1 let k= k-1 return 1+ halfit(k);
}

So to do $25$ you do:

Is $25= 0$? Nope; Is $24 = 0$? Nope;

Okay, we have to go lower to $23$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $A$ will add $1$. But for now we need to do $23$. $halfit(25) = 1+ halfit(23);$

Is $23= 0$? Nope; Is $22 = 0$? Nope;

Okay, we have to go lower to $21$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $B$ will add $1$. But for now we need to do $21$. $halfit(23) = 1+ halfit(21);$

Is $21= 0$? Nope; Is $20 = 0$? Nope;

Okay, we have to go lower to $19$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $C$ will add $1$. But for now we need to do $19$. $halfit(21) = 1+ halfit(19);$

Is $19= 0$? Nope; Is $18 = 0$? Nope;

Okay, we have to go lower to $17$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $D$ will add $1$. But for now we need to do $17$. $halfit(19) = 1+ halfit(17);$

Is $17= 0$? Nope; Is $16 = 0$? Nope;

Okay, we have to go lower to $15$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $E$ will add $1$. But for now we need to do $15$. $halfit(17) = 1+ halfit(15);$

Is $15= 0$? Nope; Is $14 = 0$? Nope;

Okay, we have to go lower to $13$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $F$ will add $1$. But for now we need to do $13$. $halfit(15) = 1+ halfit(13);$

Is $13= 0$? Nope; Is $12 = 0$? Nope;

Okay, we have to go lower to $11$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $G$ will add $1$. But for now we need to do $11$. $halfit(13) = 1+ halfit(11);$

Is $11= 0$? Nope; Is $10 = 0$? Nope;

Okay, we have to go lower to $9$ but w've gone down by $2$. We'll have adjust by $1$ on our way back: At $H$ will add $1$. But for now we need to do $9$. $halfit(11) = 1+ halfit(9);$

Is $9= 0$? Nope; Is $8 = 0$? Nope;

Okay, we have to go lower to $7$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $I$ will add $1$. But for now we need to do $7$. $halfit(9) = 1+ halfit(7);$

Is $7= 0$? Nope; Is $6 = 0$? Nope;

Okay, we have to go lower to $5$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $J$ will add $1$. But for now we need to do $5$.. $halfit(7) = 1+ halfit(5);$

Is $5= 0$? Nope; Is $4 = 0$? Nope;

Okay, we have to go lower to $3$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $K$ will add $1$. But for now we need to do $3$. $halfit(5) = 1+ halfit(3);$

Is $3= 0$? Nope; Is $2 = 0$? Nope;

Okay, we have to go lower to $1$ but we've gone down by $2$. We'll have adjust by $1$ on our way back: At $L$ will add $1$. But for now we need to do $1$.. $halfit(3) = 1+ halfit(1);$

Is $1 =0$? Nope; Is $0 =0$ !!!!YES!!!!

So we return $halfit(1) = 0$.

L) And $halfit(3) = 1+halfit(1) = 1+0 =1$.

K) And $halfit(5) = 1+halfit(3) = 1+1 =2$.

J) And $halfit(7) = 1+halfit(5) = 1+2 =3$.

I) And $halfit(9) = 1+halfit(7) = 1+3 =4$.

H) And $halfit(11) = 1+halfit(9) = 1+4 =5$.

G) And $halfit(13) = 1+halfit(11) = 1+5 =6$.

F) And $halfit(15) = 1+halfit(13) = 1+6 =7$.

E) And $halfit(17) = 1+halfit(15) = 1+7 =8$.

D) And $halfit(19) = 1+halfit(17) = 1+8 =9$.

C) And $halfit(21) = 1+halfit(19) = 1+9 =10$.

B) And $halfit(23) = 1+halfit(21) = 1+10 =11$

A) And $halfit(25) = 1+halfit(23) = 1+11 =12$

And that's it. $halfit(25) =12$

Hopefully this is clear. You had to subtract $1$ twice to get to the next step. You can't ever actually divide in half. You can only subtract. So you have to come up with something that if you repeat recursively will be the same as dividing in half.

This is how you do that. You define something that works for $0$ and $1$. And then if you start at somewhere higher than $0$ or $1$ you go down to get to the next pair lower. That is subtract $1$ twice. But then when you finish you must do something to get you back up. That's adding one when you are done.

Notice you NEVER did any division.

The key is $halfit()$ is defined for $0$ or $1$ but for $x > 1$ you can only define $halfit(x)$ in terms of $halfit(x-2)$ as $halfit(x) = 1+halfit(x-2)$.