Integer to Binary Using Recursion

Problem:
Get binary equivalent of a number using Recursion.
getBinary(2)       = 10
getBinary(5)       = 101
getBinary(1024) = 10000000000

Iterative implementation of this problem is quite trivial. But here it's expected to be done recursively!

Approach 1

The approach is quite simple -  Divide the decimal value by 2 and write down the remainder. Repeat this process until you can't divide anymore. 

Calculate for 13,

 13/2 = 6 and remainder = 1

 6/2   = 3 and remainder = 0

 3/2   = 1 and remainder = 1

 1/2   = 0 and remainder = 1        

To get binary, we write down the value of reminder from bottom to top. So it gives 1101. Let's apply recursive thinking to solve this problem. 

Subproblem will be dividing the number by 2 in each iteration. 

Base Case - binary of 1 is 1 (or 0 is 0) . 

Combining subproblem result might be tricky as it needs to be done in a reverse way. This can be achieved if the method is called first (and then the remainder operation is performed). This will ensure that the remainder is performed only when base case is reached.

public static String getBinary(int num) {
 if (num < 2) {
  return "" + num;
 }

 return getBinary(num / 2) + num % 2;
}

Stack Progress
getBinary(13)
    --> getBinary(13/2) + 13%2
             --> getBinary(6/2) + 6%2
                     -->getBinary(3/2) + 3%2
                             -->getBinary(1)    //base case, return 1
                     --> ""+ 1+ 1
             --> ""+1+1+0
     -->""+1+1+0+1   

Approach 2

Let's explore on another approach which uses bit manipulation to generate a binary equivalent. 

Binary of 5 is 101. Now let's see if we can get the bit values (1, 0 and 1) of the number by some bit manipulation technique. 

5 & 100 = 100   

5 & 010 = 000

5 & 001 = 001

Notice that, And operation (&) is performed with a number whose all values are 0 except leftmost position. And then that keeps on shifting to the right side. And the output will be 1 at that position if the bit value is 1 in the number (and 0 otherwise).

When you apply recursive thinking, it's quite clear that method needs another argument which will help in getting bit value at a given position. Integer in Java is 32 bit long, so that number will take the initial value of 1 << 31 (i.e. leftmost bit is 1 and rest all are 0). And when all bit positions (from MSB to LSB) are explored the recursion should stop. 

public static String getBinary2(int num, int and){
 if(and == 0){
      return "";   //if all bits are checked; just return
 }

 /**
  * If value at position is 1 in num; it will give and value
  */
 int t = (num & and) == and ? 1 : 0;
 
 return ""+ t + getBinary2(num, and >>> 1);
}

String binary = getBinary2(5, 1<<31);

//binary = 00000000000000000000000000000101

Can you try to come up with stack progress as shown for first approach?
Do post your feedback/doubts below!
---
keep coding !!!