printbinary рекурсивного алгоритма

Question

я не могу обернуть мою голову вокруг, как работает эта простая рекурсивная функция:

void printBinary(const int& n) 
{ 
    if(n < 2) 
    { 
     cout << n; 
    } 
    else 
    { 
     printBinary(n/2); 
     printBinary(n % 2); 
    } 
} 

Я знаю, что есть что-то делать с п/2 «рубить» с последней цифрой двоичного представления и n% 2, давая такую ​​последнюю цифру двоичного представления, но когда я рекурсивно отслеживаю этот код, он просто кажется магическим. Я не могу придумать простого логического объяснения.

Edit: This является отличным объяснением алгоритма, и ведет меня к виду перефразировать мой вопрос: почему п% 2, или остаток десятичного числа, дают вам двоичные цифры такого числа. Какова логика этого?

Answer 1

Для рекурсивного алгоритма, я всегда нахожу это полезно, чтобы быстро написать небольшой пример в текстовом файле с углублениями, чтобы показать уровни RECURSE:

f(42) 
    f(21) 
     f(10) 
      f(5) 
       f(2) 
        f(1) - 1 
        f(0) - 0 
       f(1) - 1 
      f(0) - 0 
     f(1) - 1 
    f(0) - 0 

Это эквивалентно дерево в двоичной системе, что может помощь:

f(101010b) 
    f(10101b) 
     f(1010b) 
      f(101b) 
       f(10b) 
        f(1b) - 1 
        f(0b) - 0 
       f(1b) - 1 
      f(0b) - 0 
     f(1b) - 1 
    f(0b) - 0 

что вы будете видеть из этого является то, что первый рекурсивный вызов (п/2) будет держать разделив на 2 до тех пор, пока не найдет значащий бит, сколько раз она рекурсивно является количество бит в ответе. Сколько раз вы можете разделить 42 на 2, прежде чем перейти к 1 или 0? 6 раз, поэтому в ответе есть 6 полных битов.

Следующий шаг менее очевиден. Когда вы переходите к следующему уровню - f (2) или f (10b), то, что вы сделали, идентифицируется двумя наиболее значимыми цифрами. Посмотрите на десятичное значение, которое может быть менее запутанным.

f(1234) 
    f(123) 
     f(12) 
      f(1) - 1 
      f(2) - 2 
     f(3) - 3 
    f(4) - 4 

Когда вы продолжаете делиться на 10, вы всегда имеете некоторое количество наиболее значимых цифр. Когда вы добираетесь до последних двух цифр (12), первый из них составляет 12/10, а второй - 12% 10. Возвращаясь к уровню, (123), вы уже рекурсивно позаботились о первых двух самых сиг-цифрах, f (12), и теперь вы запустите f (3), которые в десятичном дворе будут частью базового случая (n < 10).

Надеюсь, что это поможет