Может ли кто-нибудь объяснить, как работает этот алгоритм разделения?

Question

Я видел это в учебнике алгоритмов. Я запутался в средней рекурсивной функции. Если вы можете объяснить это примером, например 4/2, это было бы здорово!

function divide(x, y) 
Input: Two n-bit integers x and y, where y ≥ 1 
Output: The quotient and remainder of x divided by y 

if x = 0: return (q, r) = (0, 0) 
(q, r) = divide(floor(x/2), y) 
q = 2 · q, r = 2 · r 
if x is odd: r = r + 1 
if r ≥ y: r = r − y, q = q + 1 
return (q, r) 

Answer 1

Вы видите, сколько раз он делится на 2. Это, по существу, выполняет битовые сдвиги и работает на двоичных цифр. Более интересным случаем будет 13/3 (13 - 1101 в двоичном формате).

divide(13, 3) // initial binary value - 1101 
    divide(6, 3) // shift right - 110 
    divide(3, 3) // shift right - 11 
     divide(1, 3) // shift right - 1 (this is the most significant bit) 
     divide(0, 3) // shift right - 0 (no more significant bits) 
     return(0, 0) // roll it back up 
     return(0, 1) // since x is odd (1) 
    return(1, 0) // r = r * 2 = 2; x is odd (3) so r = 3 and the r > y condition is true  
    return(2, 0) // q = 2 * 1; r = 2 * 1 - so r >= y and q = 2 + 1 
return(4, 1) // q = 2 * 2; x is odd to r = 0 + 1