Problem Statement

Convert a decimal number to its binary equivalent using recursion.

Examples

Example 1:

Input: n = 13
Output: 1101
Explanation:
Initially, we have n = 13
Dividing 13 by 2, we get quotient = 6 and remainder = 1.
Dividing 6 by 2, we get quotient = 3 and remainder = 0.
Dividing 3 by 2, we get quotient = 1 and remainder = 1.
Dividing 1 by 2, we get quotient = 0 and remainder = 1.
Hence, the binary equivalent is 1101.

Theory

To convert a decimal number to its binary equivalent using recursion, we can follow these steps:

• Base Case: If the decimal number is 0, return 0.
• Recursive Step: Divide the decimal number by 2 and call the function recursively with the quotient.
• Concatenate the Remainder: Concatenate the remainder of the division with the result obtained from the recursive call.

Different Approaches

1️⃣ Recursion

                  decToBinary(13)
                 /              \
      remainder=1               decToBinary(6)
                               /            \
                  remainder=0             decToBinary(3)
                                         /            \
                            remainder=1             decToBinary(1)
                                                    /            \
                                       remainder=1             decToBinary(0)
                                                                |
                                                            Base Case

Code Implementation in C++:

#include <iostream>
using namespace std;

// Function to convert decimal to binary using recursion
void decToBinary(int n) {
    // Base case
    if (n == 0) {
        return;
    }

    // Recursive step
    decToBinary(n / 2);

    // Print the remainder
    cout << n % 2;
}

int main() {
    int decimalNumber = 13;

    cout << "Binary equivalent of " << decimalNumber << " is ";
    decToBinary(decimalNumber);

    return 0;
}

Output:

Binary equivalent of 13 is 1101

Explanation:

• At each step, we divide the decimal number by 2 and call decToBinary() recursively with the quotient.
• We print the remainder at each step.
• The process continues until the decimal number becomes 0.

Complexity Analysis

• Time Complexity:O(log n)
  • Since the number of recursive calls is proportional to the number of digits in the binary representation of the decimal number n.
• Space Complexity:O(log n)
  • Due to the recursive calls, the space required on the stack is proportional to the number of digits in the binary representation of the decimal number n.

2️⃣ Return Number with Recursion

When you want to convert a decimal number (base 10) into a binary number (base 2), you repeatedly divide the number by 2, noting the remainder at each step. These remainders, when read in reverse order, give the binary equivalent.

#include <bits/stdc++.h>
using namespace std;
 
// Decimal to binary conversion
// using recursion
int find(int decimal_number)
{
    if (decimal_number == 0) 
        return 0; // Base case: if the decimal number is 0, return 0.
    else
        return (decimal_number % 2 + 10 * 
                find(decimal_number / 2)); Recursive case
}
 
// Driver code 
int main()
{
    int decimal_number = 10;
    cout << find(decimal_number);
    return 0;
}

Explanation:

• Working: 
  • decimal_number % 2: This finds the remainder when the decimal number is divided by 2. The remainder is either 0 or 1, which corresponds to the current least significant bit in the binary number.
  • find(decimal_number / 2): This is the recursive call, where we reduce the decimal number by dividing it by 2. The idea is to keep dividing the number by 2 to process the next bit (since dividing by 2 shifts the number to the right in binary representation).
  • 10 * find(decimal_number / 2): This part shifts the previously computed binary digits to the left (by multiplying by 10) to make room for the new bit at the least significant position. Since binary numbers are expressed in base-2 and the result is being built as a decimal representation, multiplying by 10 moves the bits to their correct positions.

How it Works:

• Each time the function recurses, it computes the binary digit for the current division step (either 0 or 1).
• It then adds this digit to the result obtained from the previous recursive calls, shifting the result left by one position using multiplication by 10.
• The recursion continues until the decimal number becomes 0, at which point the recursion terminates and all the binary digits have been computed.

Dry Run:

Converting 13 to Binary

• Initial call: find(13)
  • 13 % 2 = 1 (this is the least significant bit).
  • Recursively call find(13 / 2 = 6).
• Second call: find(6)
  • 6 % 2 = 0 (next bit).
  • Recursively call find(6 / 2 = 3).
• Third call: find(3)
  • 3 % 2 = 1 (next bit).
  • Recursively call find(3 / 2 = 1).
• Fourth call: find(1)
  • 1 % 2 = 1 (next bit).
  • Recursively call find(1 / 2 = 0).
• Fifth call (base case): find(0)
  • return 0 because decimal_number == 0.

Now, let's unwind the recursion and build the binary number:

• From the fourth call (find(1)):
  • The result is 1 + 10 * find(0)
  • = 1 + 10 * 0 = 1.
• From the third call (find(3)):
  • The result is 1 + 10 * 1 = 1 + 10 = 11.
• From the second call (find(6)):
  • The result is 0 + 10 * 11 = 0 + 110 = 110.
• From the first call (find(13)):
  • The result is 1 + 10 * 110 = 1 + 1100 = 1101.

So, the binary equivalent of 13 is 1101.

OR:

#include <iostream>

using namespace std;

// Function to convert a decimal number to binary using recursion
int decimalToBinary(int number) {
    // Base case: If the number is 0, return 0
    if (number == 0) {
        return 0;
    }

    // Recursive case:
    // Divide the number by 2 and recursively convert the quotient
    // Multiply the result by 10 and add the remainder (number % 2)
    return decimalToBinary(number / 2) * 10 + number % 2;
}

int main() {
    int number = 8; // Input number
    cout << "Binary representation of " << number << " is: " << decimalToBinary(number) << endl;
    return 0;
}

Limitations:

1. Integer Overflow:
   For large numbers like 1024, the binary representation (10000000000) may exceed the capacity of an int. To handle this, consider using a string for the binary result.
2. Alternative with string:
   Here’s an alternative implementation using a string to avoid overflow:

#include <iostream>
using namespace std;

string decimalToBinary(int number) {
    if (number == 0) {
        return "0";
    }

    if (number == 1) {
        return "1";
    }

    return decimalToBinary(number / 2) + to_string(number % 2);
}

int main() {
    int number = 1024;
    cout << "Binary representation of " << number << " is: " << decimalToBinary(number) << endl;
    return 0;
}