Question 2 - Base Conversion Functions

Source: Data Representation, Question 2

This note explains the recursive and non-recursive Python functions in a beginner-friendly way. The code deliberately uses more steps and comments instead of trying to be short.

The question requires:

• denary values to use the integer data type;
• binary and hexadecimal values to use the string data type;
• one non-recursive and one recursive function for each conversion.

The functions below do not use shortcuts such as bin(), hex() or int(value, base).

Assumption

The functions assume that the input is valid and represents a non-negative number. Input validation can be added separately.

Symbols used in the code

Python code	Meaning	Example
//	Integer division: gives the quotient	13 // 2 gives 6
%	Modulus: gives the remainder	13 % 2 gives 1
text[-1]	Last character	"1101"[-1] gives "1"
text[:-1]	Everything except the last character	"1101"[:-1] gives "110"
text[0]	First character	"6D"[0] gives "6"
text[1:]	Everything except the first character	"6D"[1:] gives "D"
text[-4:]	Last four characters	"10110"[-4:] gives "0110"
text[:-4]	Everything except the last four characters	"10110"[:-4] gives "1"

Non-recursive versus recursive

Non-recursive function

A non-recursive function uses a loop such as while or for to repeat an operation.

while something_is_true:
    # Perform one step
    # Change the value so the loop eventually stops

Recursive function

A recursive function calls itself. It needs three parts:

def recursive_function(problem):
    # 1. Base case: the smallest possible problem
    if problem_is_small_enough:
        return simple_answer
 
    # 2. Make the problem smaller
    smaller_problem = ...
 
    # 3. Solve the smaller problem by calling the same function
    smaller_answer = recursive_function(smaller_problem)
 
    # 4. Use the smaller answer to construct the full answer
    full_answer = ...
    return full_answer

If there is no base case, the function will continue calling itself until Python reports an error.

Shared hexadecimal helper

Hexadecimal needs the digits A to F. The string below lets us convert between a value and its hexadecimal character.

HEX_DIGITS = "0123456789ABCDEF"
 
 
def hex_digit_value(character):
    # Convert the character to uppercase so both "d" and "D" work.
    uppercase_character = character.upper()
 
    # Find the position of the character in HEX_DIGITS.
    # For example, "D" is at position 13.
    value = HEX_DIGITS.index(uppercase_character)
 
    return value

Examples:

HEX_DIGITS[13]          # Gives "D"
hex_digit_value("D")   # Gives 13
hex_digit_value("f")   # Gives 15

---

(a) Denary to binary

Algorithm

1. Divide the denary number by 2.
2. Record the remainder, which will be 0 or 1.
3. Continue converting the quotient.
4. Put each new remainder at the front of the answer.

For example, converting 13:

13 // 2 = 6, remainder 1
 6 // 2 = 3, remainder 0
 3 // 2 = 1, remainder 1
 1 // 2 = 0, remainder 1
 
Read the remainders from bottom to top: 1101

Non-recursive version

def decimal_to_binary(number):
    # Zero is a special case because the loop below only runs
    # while the number is greater than zero.
    if number == 0:
        return "0"
 
    # The answer is a string because binary numbers must be returned
    # using the string data type.
    binary_answer = ""
 
    # Keep converting until the quotient becomes zero.
    number_still_to_convert = number
 
    while number_still_to_convert > 0:
        # Find the remainder after division by 2.
        remainder = number_still_to_convert % 2
 
        # Convert the integer remainder to a string.
        binary_digit = str(remainder)
 
        # Put the digit at the FRONT because the first remainder
        # is the least significant digit.
        binary_answer = binary_digit + binary_answer
 
        # Continue using the quotient.
        quotient = number_still_to_convert // 2
        number_still_to_convert = quotient
 
    return binary_answer

Recursive version

def decimal_to_binary_recursive(number):
    # Base case:
    # 0 in binary is "0", and 1 in binary is "1".
    if number < 2:
        answer = str(number)
        return answer
 
    # Make the problem smaller by dividing the number by 2.
    quotient = number // 2
 
    # The remainder is the final binary digit for this call.
    remainder = number % 2
    current_binary_digit = str(remainder)
 
    # Recursively convert the smaller quotient.
    binary_for_quotient = decimal_to_binary_recursive(quotient)
 
    # The quotient contains the more significant digits, so it comes first.
    answer = binary_for_quotient + current_binary_digit
 
    return answer

Recursive trace for 13

decimal_to_binary_recursive(13)
= decimal_to_binary_recursive(6) + "1"
= decimal_to_binary_recursive(3) + "0" + "1"
= decimal_to_binary_recursive(1) + "1" + "0" + "1"
= "1" + "1" + "0" + "1"
= "1101"

Common mistake

current_binary_digit + binary_for_quotient gives the digits in the wrong order. The answer from the recursive call must come first.

---

(b) Denary to hexadecimal

This is almost identical to denary-to-binary conversion. The differences are:

• divide by 16 instead of 2;
• use HEX_DIGITS to turn remainders from 10 to 15 into A to F.

Non-recursive version

def decimal_to_hexadecimal(number):
    if number == 0:
        return "0"
 
    hexadecimal_answer = ""
    number_still_to_convert = number
 
    while number_still_to_convert > 0:
        # Find the remainder after division by 16.
        remainder = number_still_to_convert % 16
 
        # Use the remainder as a position in HEX_DIGITS.
        # For example, HEX_DIGITS[15] is "F".
        hexadecimal_digit = HEX_DIGITS[remainder]
 
        # Put the new digit at the front of the answer.
        hexadecimal_answer = hexadecimal_digit + hexadecimal_answer
 
        # Continue using the quotient.
        quotient = number_still_to_convert // 16
        number_still_to_convert = quotient
 
    return hexadecimal_answer

Recursive version

def decimal_to_hexadecimal_recursive(number):
    # Base case:
    # Any value below 16 needs only one hexadecimal digit.
    if number < 16:
        hexadecimal_digit = HEX_DIGITS[number]
        return hexadecimal_digit
 
    # Make the problem smaller by dividing by 16.
    quotient = number // 16
 
    # Find the final hexadecimal digit for this call.
    remainder = number % 16
    current_hexadecimal_digit = HEX_DIGITS[remainder]
 
    # Recursively convert the quotient.
    hexadecimal_for_quotient = decimal_to_hexadecimal_recursive(quotient)
 
    # Put the more significant digits before the current digit.
    answer = hexadecimal_for_quotient + current_hexadecimal_digit
 
    return answer

Example:

79 // 16 = 4, remainder 15
HEX_DIGITS[15] = "F"
 
Answer: "4F"

---

(c) Binary to denary

Instead of calculating every power of 2 separately, process the binary digits from left to right:

new total = old total * 2 + new digit

For 1101:

Start at 0
Read 1: 0 * 2 + 1 = 1
Read 1: 1 * 2 + 1 = 3
Read 0: 3 * 2 + 0 = 6
Read 1: 6 * 2 + 1 = 13

Non-recursive version

def binary_to_decimal(binary):
    decimal_answer = 0
 
    # Visit each character from left to right.
    for current_bit_character in binary:
        # The character is "0" or "1".
        # Convert it to the integer 0 or 1.
        current_bit_value = int(current_bit_character)
 
        # Multiplying by 2 shifts the existing binary value left.
        shifted_answer = decimal_answer * 2
 
        # Add the current bit.
        decimal_answer = shifted_answer + current_bit_value
 
    return decimal_answer

Recursive version

def binary_to_decimal_recursive(binary):
    # Base case:
    # An empty binary prefix contributes a value of zero.
    if binary == "":
        return 0
 
    # Split the string into two parts.
    prefix = binary[:-1]              # Everything except the last bit
    last_bit_character = binary[-1]   # The last bit
 
    # Convert the last bit from a string to an integer.
    last_bit_value = int(last_bit_character)
 
    # Recursively find the value of the prefix.
    prefix_value = binary_to_decimal_recursive(prefix)
 
    # Shift the prefix left by multiplying it by 2.
    shifted_prefix_value = prefix_value * 2
 
    # Add the final bit.
    answer = shifted_prefix_value + last_bit_value
 
    return answer

Recursive trace for 1101

value("1101") = value("110") * 2 + 1
value("110")  = value("11")  * 2 + 0
value("11")   = value("1")   * 2 + 1
value("1")    = value("")    * 2 + 1
value("")     = 0

---

(d) Hexadecimal to denary

The method is the same as binary to denary, except the previous value is multiplied by 16:

new total = old total * 16 + new digit value

Non-recursive version

def hexadecimal_to_decimal(hexadecimal):
    decimal_answer = 0
 
    for current_hexadecimal_character in hexadecimal:
        # Convert a character such as "D" into the integer 13.
        current_digit_value = hex_digit_value(
            current_hexadecimal_character
        )
 
        # Shift the existing hexadecimal value one place left.
        shifted_answer = decimal_answer * 16
 
        # Add the value of the current hexadecimal digit.
        decimal_answer = shifted_answer + current_digit_value
 
    return decimal_answer

Recursive version

def hexadecimal_to_decimal_recursive(hexadecimal):
    # Base case:
    # An empty hexadecimal prefix contributes zero.
    if hexadecimal == "":
        return 0
 
    # Separate the last hexadecimal digit from the prefix.
    prefix = hexadecimal[:-1]
    last_digit_character = hexadecimal[-1]
 
    # Convert the final hexadecimal character to its integer value.
    last_digit_value = hex_digit_value(last_digit_character)
 
    # Recursively convert the prefix.
    prefix_value = hexadecimal_to_decimal_recursive(prefix)
 
    # Shift the prefix one hexadecimal place to the left.
    shifted_prefix_value = prefix_value * 16
 
    # Add the final hexadecimal digit.
    answer = shifted_prefix_value + last_digit_value
 
    return answer

Example for 6D:

value("6D") = value("6") * 16 + value("D")
             = 6 * 16 + 13
             = 109

---

(e) Binary to hexadecimal

Algorithm

1. Starting from the right, divide the binary string into groups of four bits.
2. Add zeros to the left if the first group has fewer than four bits.
3. Convert every group to a value from 0 to 15.
4. Use that value to select a character from HEX_DIGITS.

First, create a helper that converts up to four binary bits into denary.

def binary_group_to_decimal(binary_group):
    group_value = 0
 
    for current_bit_character in binary_group:
        current_bit_value = int(current_bit_character)
 
        shifted_group_value = group_value * 2
        group_value = shifted_group_value + current_bit_value
 
    return group_value

Non-recursive version

def binary_to_hexadecimal(binary):
    # Remove unnecessary leading zeros.
    binary_without_leading_zeros = binary.lstrip("0")
 
    # If every character was zero, the correct answer is "0".
    if binary_without_leading_zeros == "":
        binary_without_leading_zeros = "0"
 
    binary_to_process = binary_without_leading_zeros
 
    # Add zeros to the left until the length is a multiple of four.
    while len(binary_to_process) % 4 != 0:
        binary_to_process = "0" + binary_to_process
 
    hexadecimal_answer = ""
    current_position = 0
 
    # Process one group of four bits at a time.
    while current_position < len(binary_to_process):
        group_end_position = current_position + 4
 
        current_group = binary_to_process[
            current_position:group_end_position
        ]
 
        # Convert the four-bit group to a value from 0 to 15.
        group_value = binary_group_to_decimal(current_group)
 
        # Convert the value into one hexadecimal character.
        hexadecimal_digit = HEX_DIGITS[group_value]
 
        # Add the character to the answer.
        hexadecimal_answer = hexadecimal_answer + hexadecimal_digit
 
        # Move to the next four-bit group.
        current_position = current_position + 4
 
    return hexadecimal_answer

Recursive version

The smaller problem is the binary string with its final four bits removed.

def binary_to_hexadecimal_recursive(binary):
    # Base case:
    # Four or fewer bits can be represented by one hexadecimal digit.
    if len(binary) <= 4:
        group_value = binary_to_decimal_recursive(binary)
        hexadecimal_digit = HEX_DIGITS[group_value]
        return hexadecimal_digit
 
    # Split the string into the prefix and its final group of four bits.
    prefix = binary[:-4]
    last_four_bits = binary[-4:]
 
    # Recursively convert the prefix first.
    hexadecimal_for_prefix = binary_to_hexadecimal_recursive(prefix)
 
    # Convert the final group into one hexadecimal digit.
    last_group_value = binary_to_decimal_recursive(last_four_bits)
    last_hexadecimal_digit = HEX_DIGITS[last_group_value]
 
    # The prefix contains the more significant digits, so it comes first.
    answer = hexadecimal_for_prefix + last_hexadecimal_digit
 
    return answer

Example for 10110:

Split from the right:
 
prefix = "1"
last four bits = "0110"
 
"1"    becomes hexadecimal "1"
"0110" becomes denary 6, then hexadecimal "6"
 
Answer: "16"

Note

This simple recursive version may preserve an unnecessary leading hexadecimal zero if the binary input begins with many zeros. The numerical value is still correct. You can remove leading zeros before calling it if required.

---

(f) Hexadecimal to binary

Each hexadecimal digit becomes exactly four binary digits.

Examples:

2 -> 0010
A -> 1010
F -> 1111

Non-recursive four-bit helper

def decimal_value_to_four_bit_binary(value):
    four_bit_answer = ""
    bits_created = 0
    value_still_to_convert = value
 
    # Always create exactly four bits, including leading zeros.
    while bits_created < 4:
        remainder = value_still_to_convert % 2
        current_binary_digit = str(remainder)
 
        # Add the current bit to the front.
        four_bit_answer = current_binary_digit + four_bit_answer
 
        # Continue using the quotient.
        quotient = value_still_to_convert // 2
        value_still_to_convert = quotient
 
        bits_created = bits_created + 1
 
    return four_bit_answer

Non-recursive conversion

def hexadecimal_to_binary(hexadecimal):
    binary_answer = ""
 
    for current_hexadecimal_character in hexadecimal:
        # Convert the hexadecimal character to a value from 0 to 15.
        current_value = hex_digit_value(
            current_hexadecimal_character
        )
 
        # Convert that value into exactly four binary bits.
        current_four_bits = decimal_value_to_four_bit_binary(
            current_value
        )
 
        # Add the four bits to the answer.
        binary_answer = binary_answer + current_four_bits
 
    return binary_answer

Recursive four-bit helper

def decimal_value_to_four_bit_binary_recursive(value, places_left):
    # Base case:
    # Stop after exactly four binary places have been produced.
    if places_left == 0:
        return ""
 
    quotient = value // 2
    remainder = value % 2
    current_binary_digit = str(remainder)
 
    # Recursively create the earlier binary positions.
    earlier_binary_digits = (
        decimal_value_to_four_bit_binary_recursive(
            quotient,
            places_left - 1
        )
    )
 
    # Put the current remainder at the end.
    answer = earlier_binary_digits + current_binary_digit
 
    return answer

Recursive conversion

The smaller problem is the hexadecimal string with its first character removed.

def hexadecimal_to_binary_recursive(hexadecimal):
    # Base case:
    # An empty hexadecimal string produces no more binary digits.
    if hexadecimal == "":
        return ""
 
    # Separate the first hexadecimal character from the rest.
    first_hexadecimal_character = hexadecimal[0]
    remaining_hexadecimal_characters = hexadecimal[1:]
 
    # Convert the first hexadecimal character to a value from 0 to 15.
    first_digit_value = hex_digit_value(
        first_hexadecimal_character
    )
 
    # Convert this value into exactly four bits.
    first_four_binary_bits = (
        decimal_value_to_four_bit_binary_recursive(
            first_digit_value,
            4
        )
    )
 
    # Recursively convert the remaining hexadecimal characters.
    binary_for_remaining_characters = (
        hexadecimal_to_binary_recursive(
            remaining_hexadecimal_characters
        )
    )
 
    # Join the current four bits to the answer for the remaining digits.
    answer = (
        first_four_binary_bits
        + binary_for_remaining_characters
    )
 
    return answer

Example for 2A:

hexadecimal_to_binary_recursive("2A")
 
First digit: "2" -> "0010"
Remaining string: "A"
 
First digit: "A" -> "1010"
Remaining string: "" -> base case
 
Answer: "0010" + "1010" = "00101010"

---

Test cases

Place these tests after all the function definitions:

print(decimal_to_binary(79))
print(decimal_to_binary_recursive(79))
# Both should display: 1001111
 
print(decimal_to_hexadecimal(79))
print(decimal_to_hexadecimal_recursive(79))
# Both should display: 4F
 
print(binary_to_decimal("100"))
print(binary_to_decimal_recursive("100"))
# Both should display: 4
 
print(hexadecimal_to_decimal("6D"))
print(hexadecimal_to_decimal_recursive("6D"))
# Both should display: 109
 
print(binary_to_hexadecimal("10110"))
print(binary_to_hexadecimal_recursive("10110"))
# Both should display: 16
 
print(hexadecimal_to_binary("FF60"))
print(hexadecimal_to_binary_recursive("FF60"))
# Both should display: 1111111101100000

How to design the recursive versions yourself

Conversion	Smaller version of the problem	Base case	How to combine
Denary to binary	number // 2	number < 2	Append number % 2
Denary to hexadecimal	number // 16	number < 16	Append HEX_DIGITS[number % 16]
Binary to denary	Remove final bit using binary[:-1]	Empty string	Multiply prefix by 2 and add final bit
Hexadecimal to denary	Remove final digit using hexadecimal[:-1]	Empty string	Multiply prefix by 16 and add final digit
Binary to hexadecimal	Remove final four bits using binary[:-4]	At most four bits	Append the hexadecimal digit for the last group
Hexadecimal to binary	Remove first digit using hexadecimal[1:]	Empty string	Put the current four-bit group before the remaining answer

Two patterns worth memorising

Denary to another base

1. Divide the number by the base.
2. Recursively convert the quotient.
3. Append the remainder's digit.

Another base to denary

1. Remove the final digit.
2. Recursively find the prefix's value.
3. Multiply that value by the base.
4. Add the final digit's value.

Tip

When you are stuck, do not start by writing the recursive call. First write the base case, then ask: What smaller input represents the same conversion problem?