The following algorithm can be used for division. Can someone intuitively explain or offer proof that quotient returned from recursive call (say q') is such that quotient that should be returned from current function call (say q) is at max one less than 2q'. I get the pattern but don't understand it well enough.
divide(x,y):
if (y>x) return 0
q = divide (x, 2*y)
if ((x-2*q*y)<y)
return 2*q
else
return 2*q+1
The algorithm is doing long division in base $2$. For example: $$34 = 10\,0010_b\\6=110_b$$ Doing long division: $$\require{enclose}\begin{array}{r} 101\\[-3pt] 110 \enclose{longdiv}{100010}\\[-3pt] -\underline{110\phantom{00}}\\[-3pt] 01010\\[-3pt] -\underline{000\phantom{0}}\\[-3pt] 1010\\[-3pt] -\underline{110}\\[-3pt] 100 \end{array}$$ giving a quotient of $101_b = 5$ and a remainder of $100_b = 4$.
The algorithm starts by moving the divisor $y$ to the left (by doubling it) until the result of subtracting from $x$ gives a result less than the moved $y$ (actually it goes one move further, but returns $0$ for that level, effectvely making the previous call the first one of consequence). This gives $$\begin{array}{r} 1\\[-3pt] 110 \enclose{longdiv}{100010}\\[-3pt] -\underline{110\phantom{00}}\\[-3pt] 01010 \end{array}$$ with $q = 1$ being the value on top. at the next level down, $q$ is multiplied by $2$, moving one place left. So now the remainder is $x - (2q)y$. If this is big enough that we can subtract out one more $y$, then we add a $1$ to the quotient as well. In the example, it wasn't big enough, so we end up with that bit being $0$: $$\begin{array}{r} 10\\[-3pt] 110 \enclose{longdiv}{100010}\\[-3pt] -\underline{110\phantom{00}}\\[-3pt] 01010\\[-3pt] -\underline{000\phantom{0}}\\[-3pt] 1010 \end{array}$$ At the next level, we multiply $q$ by $2$ again. Notice that $x - (2q)y$ is big enough that we can subtract out one more $y$, so we end up adding $1$ to $2q$ to account for it.
And then we discover we are at the bottom. The remainder is below the original divisor $y$ and the process stops.