Convert Decimal 13 to Binary by Delaying Each Remainder

Dividing by 2 reveals the next binary digit from the right

When you divide a decimal number by 2, the remainder is either 0 or 1, so it gives one binary digit. For 13, integer division by 2 gives a quotient of 6 and a remainder of 1. Repeating the same operation on each quotient reaches 0.

The remainders are discovered in the order 1, 0, 1, 1. That is not the order of the binary representation. The first remainder belongs to the rightmost digit, because it describes the lowest place value. The last remainder belongs to the leftmost digit, so the output must be 1, 1, 0, 1, which is 1101.

Printing after the recursive call puts the digits in the correct order

The recursive call can delay each remainder until the smaller number has been processed. The function first calls itself with n divided by 2, then prints n modulo 2. Calls descend from 13 to 6 to 3 to 1 to 0. When the call at 0 returns, the calls finish in the opposite order: 1, 3, 6, and 13.

void printBinary(int n) {
    if (n == 0) return;

    printBinary(n / 2);
    cout << n % 2;
}

The call for 1 prints its remainder 1 first. Then the call for 3 prints 1, the call for 6 prints 0, and the call for 13 prints 1. The output is therefore 1101. If the output statement came before the recursive call, each remainder would be printed as soon as it was discovered, producing 1011 instead.

The zero call stops without adding a leading digit

The call with n equal to 0 is the stopping condition. It returns immediately and prints nothing. That silent call is still part of the chain, because it lets the call for 1 begin unwinding, but it must not add a 0 to the result. This is why the output is 1101 rather than 01101, and why the calls do not continue forever.

For 13, the complete chain is 13, 6, 3, 1, 0. The zero call returns first. The delayed remainders are then printed by the calls for 1, 3, 6, and 13 as those calls finish.

if (____) return;

Halving the number makes both time and stack space logarithmic

Each recursive call replaces n with its quotient after division by 2. The number of calls therefore grows with how many times you can halve n before reaching 0. For 13, there are four digit-producing calls, for 13, 6, 3, and 1, followed by one base call at 0.

Each call does constant work besides the recursive call, so the running time follows T(n) = T(floor(n / 2)) + O(1). The number of halvings is logarithmic, giving O(log n) time. The maximum auxiliary stack space is also O(log n), because all calls from 13 through 6, 3, 1, and 0 are waiting before any of them can print.

For the concrete input 13, the deepest stack chain is printBinary(13), printBinary(6), printBinary(3), printBinary(1), and printBinary(0). The stack then unwinds and prints four digits. The base call adds one level to the maximum chain but performs no output.