Write a number in binary
Turn a number into its binary text by writing the answer for half the number, then the last bit. About 11 minutes.
The last bit goes last
Writing 13 in binary: divide by 2 repeatedly and record the remainders. 13 gives remainder 1, then 6 gives 0, then 3 gives 1, then 1 gives 1. The remainders come out backwards, as 1011 reversed is 1101.
Recursion fixes the order without any reversing. The text for 13 is the text for 6, followed by the last bit of 13. The call for 6 builds its text first, then you add 13's bit at the end. When the number is 0 or 1, it is already a single bit.
def to_binary(n):
if n < 2:
return str(n)
return to_binary(n // 2) + str(n % 2)to_binary(13): the last bit is 13 % 2 = 1. Ask for to_binary(6) first.
Watch the base case
The base case is any number below 2, since 0 and 1 are already one bit each. If you only stopped at 1, then 0 would loop forever, because 0 divided by 2 is still 0.
Notice the call count equals the number of bits. A number around a billion needs only about 30 calls, so recursion depth is tiny here, unlike the one-at-a-time list walks.
What does the recursive version return for 0?
- A"0", because 0 is below 2
- BAn empty string
- CIt calls itself forever
Show the answer
"0", because 0 is below 2. The base case handles 0 and 1 as single bits.
Write in binary
n is a non-negative whole number. Return its binary representation as a string of 0s and 1s with no leading zeros (0 is written as "0"), using a recursive function.
n = 13 → "1101"
0 ≤ n ≤ 1,000,000,000