Decimal to binary conversion using recursion

You're in a Microsoft phone screen, and the interviewer says, "Write me a function that takes a decimal integer and returns its binary representation as a string." They pause, then add, "And I'd like to see you do it recursively." This is one of those problems that sounds trivial at first, but it's actually a great test of whether you understand how recursion maps to a real mathematical process. The problem is also known as "Convert Decimal to Binary String" on other platforms, and it shows up regularly as a warm-up before harder recursion questions.

TL;DR

Convert a decimal integer to its minimal binary string by recursively dividing by 2. At each level, compute decimal % 2 for the current bit and recurse on decimal / 2 for the remaining bits. The base case is when the decimal is 0 or 1, which maps directly to "0" or "1". The call stack naturally builds the string in the correct left-to-right order, producing the result in O(log n) time and O(log n) space.

Why This Problem Matters

Decimal to binary conversion is a foundational recursion problem that tests three things at once: understanding of number systems, recursive decomposition, and string building. It comes up frequently at Microsoft and other companies as a warm-up, and the recursive pattern it teaches, dividing a problem in half at each step, transfers directly to binary search, merge sort, and other divide-and-conquer algorithms.

Binary Numbers: A Quick Refresher

Before diving into the solution, let's make sure we're aligned on how binary works. In the decimal system (base 10), each position represents a power of 10. In binary (base 2), each position represents a power of 2.

For example, the decimal number 10 in binary is 1010:

8 + 0 + 2 + 0 = 10. That checks out.

The manual conversion process works by repeatedly dividing the number by 2 and tracking the remainders:

• 10 / 2 = 5, remainder 0
• 5 / 2 = 2, remainder 1
• 2 / 2 = 1, remainder 0
• 1 is our base case: 1

Reading the results from bottom to top gives us 1010. This "divide and collect remainders" process is inherently recursive, which is exactly why recursion fits so well here.

Understanding the Problem

Let's pin down what we need to build:

Given: A non-negative integer (0 to 1000) Return: Its minimal binary representation as a string Minimal: No leading zeros, so 5 is "101", not "0101"

toBinary(0)  -> "0"
toBinary(1)  -> "1"
toBinary(3)  -> "11"
toBinary(5)  -> "101"
toBinary(7)  -> "111"
toBinary(10) -> "1010"

Edge Cases

1. Zero: Should return "0", not an empty string
2. One: Should return "1", the simplest non-zero case
3. Powers of two: Like 8 = "1000", only one bit set
4. Large values: 999 = "1111100111", the upper bound of our constraint

Solution Approach

The key insight is recognizing that the manual division process maps perfectly to recursion. Each recursive call handles one binary digit, and the call stack takes care of ordering.

Building Intuition

Think about it this way. If someone asked you, "What's 10 in binary?", you might think:

1. Is 10 small enough that I already know? No, 10 is bigger than 1.
2. What's the last bit? 10 % 2 = 0. So the rightmost bit is 0.
3. What about the rest? I need to figure out 5 in binary, then stick a 0 on the end.

That's recursion. You solve a smaller version of the same problem (5 instead of 10), then combine the result with the current digit.

The Recursive Structure

Here's how the recursion unfolds for toBinary(10):

Each call divides by 2 and records the remainder. When we hit the base case (1), the recursion unwinds, and we concatenate the remainders in the correct order.

Unwinding the Stack

Here's what the unwinding looks like. Watch how the binary string builds from left to right:

The call stack reverses the order of remainders for free. No need for a separate reversal step, which is one of the nice properties of this recursive approach.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here's the Java solution:

public class Solution {
  public String toBinary(int decimal) {
    // Base case: 0 and 1 map directly to their binary representation
    if (decimal <= 1) {
      return String.valueOf(decimal);
    }

    // Recurse on decimal / 2 (the higher-order bits),
    // then append decimal % 2 (the current bit)
    return toBinary(decimal / 2) + decimal % 2;
  }
}

Let's walk through toBinary(5) step by step:

1. toBinary(5): 5 > 1, so recurse with toBinary(2) and append 5 % 2 = 1
2. toBinary(2): 2 > 1, so recurse with toBinary(1) and append 2 % 2 = 0
3. toBinary(1): Base case, return "1"
4. Unwind: "1" + "0" = "10", then "10" + "1" = "101"

The two key operations at each level are:

• decimal / 2 (integer division): strips off the last binary digit, giving us the remaining higher-order bits
• decimal % 2: extracts the last binary digit (0 or 1)

By recursing first and appending the remainder after, the string naturally builds in the correct left-to-right order.

Complexity Analysis

Time Complexity: O(log n)

Each recursive call divides the input by 2, so the total number of calls is the number of bits in the binary representation: floor(log2(n)) + 1. For our constraint of n ≤ 1000, that's at most 10 levels of recursion. String concatenation at each level technically adds some overhead, but the recursion depth is the dominant factor.

Space Complexity: O(log n)

The recursion consumes O(log n) stack frames. Each frame stores the local decimal value and the partial string result. For n ≤ 1000, this means at most 10 stack frames, which is very manageable.

Why Not O(n)?

A common mistake is to say the time complexity is O(n). It's tempting because the problem description says "given an integer n", but the number of recursive calls depends on the number of bits, not the value itself. Dividing by 2 at each step gives us logarithmic depth, not linear.

Common Pitfalls

1. Forgetting the zero case: If your base case only handles decimal == 1, then toBinary(0) will loop forever. Using decimal <= 1 catches both 0 and 1 cleanly.

2. Appending before recursing: If you write decimal % 2 + toBinary(decimal / 2), the digits come out reversed. The recursive call must come first to produce the higher-order bits.

3. Using floating-point division: In languages where / defaults to float division (Python 2, for example), you need integer division. Java handles this automatically for int operands.

4. Leading zeros confusion: The problem asks for "minimal" binary, so "101" not "0101". The recursive approach naturally avoids leading zeros because the base case returns "1" (or "0" only for the input 0 itself).

Interview Tips

When this comes up in an interview:

1. Clarify constraints: "Can the input be negative? What's the maximum value?" This shows you think about edge cases before coding.

2. Explain the math first: Before writing any code, walk through the division process with a small example like 5 or 10. Most interviewers want to see that you understand the underlying algorithm.

3. State your base case explicitly: "When the number is 0 or 1, it maps directly to binary." This is the first thing to write down.

4. Mention the iterative alternative: After presenting the recursive solution, note that an iterative approach (divide in a loop, then reverse) avoids stack usage but requires manual reversal. This shows breadth of thinking.

5. Watch for the follow-up: Interviewers often follow up with "What about binary to decimal?" or "What about other bases?" The same divide-and-remainder pattern generalizes to any base conversion.

Key Takeaways

• The recursive formula toBinary(decimal / 2) + decimal % 2 with a base case of decimal ≤ 1 produces a clean, minimal binary string without manual reversal.
• Time and space are both O(log n) because each recursive call halves the input, yielding floor(log2(n)) + 1 total calls.
• The call stack naturally reverses the order of remainders, which is why the recursive call comes before the concatenation, not after.
• Always handle 0 as a base case alongside 1. Missing this causes infinite recursion on the input 0.
• This "divide and combine" recursive pattern is the same structure behind binary search and merge sort, making it a valuable building block for harder problems.

Solutions in Other Languages

Python

class Solution:
    def to_binary(self, decimal: int) -> str:
        if decimal <= 1:
            return str(decimal)

        return self.to_binary(decimal // 2) + str(decimal % 2)

Python uses // for integer division. The str() calls convert the integer remainder to a string for concatenation.

JavaScript

class Solution {
  toBinary(decimal) {
    if (decimal <= 1) {
      return decimal.toString();
    }

    return this.toBinary(Math.floor(decimal / 2)) + decimal % 2;
  }
}

JavaScript requires Math.floor() because the / operator produces floating-point results. The this. prefix is needed since toBinary is a class method.

TypeScript

class Solution {
  toBinary(decimal: number): string {
    if (decimal <= 1) {
      return decimal.toString();
    }

    return this.toBinary(Math.floor(decimal / 2)) + decimal % 2;
  }
}

Same logic as JavaScript, with type annotations for the parameter and return type.

C++

class Solution {
public:
  std::string toBinary(int decimal) {
    if (decimal <= 1) {
      return std::to_string(decimal);
    }

    return toBinary(decimal / 2) + std::to_string(decimal % 2);
  }
};

C++ integer division truncates naturally. std::to_string converts the remainder to a string for concatenation.

Scala

class Solution {
  def toBinary(decimal: Int): String = {
    if (decimal <= 1) return decimal.toString
    toBinary(decimal / 2) + decimal % 2
  }
}

Scala's concise syntax lets us express the solution in just a few lines. Integer division truncates as expected.

Kotlin

class Solution {
    fun toBinary(decimal: Int): String {
        if (decimal <= 1) {
            return decimal.toString()
        }

        return toBinary(decimal / 2) + decimal % 2
    }
}

Kotlin's toString() and integer division work the same as Java's.

Swift

class Solution {
    func toBinary(_ decimal: Int) -> String {
        if decimal <= 1 {
            return String(decimal)
        }

        return toBinary(decimal / 2) + "\(decimal % 2)"
    }
}

Swift uses String() for conversion and string interpolation \() to append the remainder.

Ruby

class Solution
  def to_binary(decimal)
    if decimal <= 1
      return decimal.to_s
    end

    return to_binary(decimal / 2) + (decimal % 2).to_s
  end
end

Ruby's integer division truncates by default. The .to_s method converts integers to strings.

Rust

impl Solution {
    pub fn to_binary(&self, decimal: i32) -> String {
        if decimal <= 1 {
            return decimal.to_string();
        }

        format!("{}{}", self.to_binary(decimal / 2), decimal % 2)
    }
}

Rust uses format! macro for string concatenation. The &self parameter follows Firecode's struct method convention.

C#

public class Solution {
    public string toBinary(int number) {
        if (number <= 1) {
            return number.ToString();
        }

        return toBinary(number / 2) + number % 2;
    }
}

C# uses ToString() and integer division truncates automatically, just like Java.

Dart

class Solution {
  String toBinary(int decimal) {
    if (decimal <= 1) {
      return decimal.toString();
    }

    return toBinary(decimal ~/ 2) + '${decimal % 2}';
  }
}

Dart uses the ~/ operator for integer division and string interpolation for the remainder.

PHP

class Solution {
    public function toBinary(int $decimal): string {
        if ($decimal <= 1) {
            return strval($decimal);
        }

        return $this->toBinary(intdiv($decimal, 2)) . ($decimal % 2);
    }
}

PHP uses intdiv() for integer division and . for string concatenation.

Practice Makes Perfect

Once you're comfortable with this problem, try these related challenges that build on the same recursive decomposition pattern:

• Power of Two - determine if a number is a power of two using bit manipulation
• Counting Set Bits in Binary - count the number of 1s in a binary representation
• Reverse an Integer - reverse digits of an integer, another recursion-friendly problem

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Whether you're brushing up on recursion fundamentals or working through advanced algorithms, consistent practice on problems like this is what separates candidates who get offers from those who don't.