Just begin with an example: write a method in Java that calculates the 2-based (binary) representation of a number using recursion.

Takes an integer as input and returns a string representing its binary form. The recursive logic is based on dividing the number by 2 and building the binary representation from the remainder of this division.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class BinaryConverter {
    public static void main(String[] args) {
        int number = 10; // Example number
        String binaryRepresentation = toBinary(number);
        System.out.println("Binary representation of " + number + " is: " + binaryRepresentation);
    }

    public static String toBinary(int number) {
        // Base case: if the number is 0 or 1, return it as a string
        if (number == 0 || number == 1) {
            return String.valueOf(number);
        }

        // Recursive call: divide the number by 2 and build the binary string
        return toBinary(number / 2) + number % 2;
    }
}

Use the example number 10 to illustrate how the code works to convert it into its binary representation using recursion.

The binary representation of the decimal number 10 is 1010. Now, let’s walk through how the toBinary method processes this number:

1. Initial Call with 10
   • The method is initially called with toBinary(10).
   • Since 10 is neither 0 nor 1, the method proceeds to the recursive call.
   • It makes a recursive call with the quotient of 10 divided by 2, which is toBinary(5), and appends the remainder of 10 % 2 (which is 0) to the result of this recursive call.
2. Recursive Call with 5
   • Now, we are in the recursive call toBinary(5).
   • 5 is neither 0 nor 1, so it again proceeds to a recursive call.
   • It calls toBinary(5 / 2) which is toBinary(2) and appends the remainder of 5 % 2 (which is 1) to the result.
3. Recursive Call with 2
   • In the call toBinary(2), 2 is still neither 0 nor 1.
   • It calls toBinary(2 / 2) which is toBinary(1) and appends the remainder of 2 % 2 (which is 0) to the result.
4. Recursive Call with 1
   • Now, we are at toBinary(1).
   • Since 1 is one of the base cases, the method returns “1”.
5. Building the Result
   • The calls start to return and the binary string is built:
     • toBinary(1) returns “1”.
     • toBinary(2) returns “1” + 0 = “10”.
     • toBinary(5) returns “10” + 1 = “101”.
     • toBinary(10) returns “101” + 0 = “1010”.

So, the binary representation of 10, as computed by the method, is “1010”.

Here is a visual breakdown of the recursive calls:

1
2
3
4
5

toBinary(10) -> toBinary(5) + "0"
             -> (toBinary(2) + "1") + "0"
             -> ((toBinary(1) + "0") + "1") + "0"
             -> (("1" + "0") + "1") + "0"
             -> "1010"

Each recursive call breaks the problem down into a smaller subproblem (dividing the number by 2 each time), and the base case (when the number is 1 or 0) provides a straightforward answer. The binary number is built as the recursive calls return, concatenating the remainders in reverse order of the calls.