# Recursive C++ solution with step by step explanation

• It takes me a lot of time to understand the solution.
So I decide to share my thought, and I hope this can help someone.

Assume a = 1 = 1, b = 7 = 111, and you want to do a + b in binary form. Intuitively, you will add them bit by bit and get the carry, like this

carry-----1 1
a-------------1
b---------1 1 1
sum---1 0 0 0

Firstly, ignore the carry, add all the bits and store the result.
But how to add without using +? Observe 0+0=0, 0+1=1, 1+0=1, 1+1 = 0, that's XOR.
So we have sum = a ^ b.

Secondly, get the carry for all the bit. Once again, observe 0+0 => carry = 0, 0+1 => carry = 0, 1+0 => carry = 0, 1+1 => carry = 1, that's AND. And you need to left shift the carry by 1, just like what you do of bit by bit add.
So we have carry = (a & b) << 1.

Then we can get the result by getSum(sum, carry), here is an example

a = 1 = 1, b = 7 = 111
sum = 1 ^ 111 = 110
carry = (1 & 111) << 1 = 10

So we get the first step of addition, and we can get the answer by calling getSum(sum, carry) recursively, just like manual addition.

But what's the end condition?
The answer is no more carry exists.

So we have the recursive algorithm. And you can rewrite it in an iterative way if you have this recursive version.

``````    int getSum(int a, int b) {
/* Recursive version */
int sum, carry;

if(b == 0)
{
return a;
}

sum = a ^ b;
carry = (a & b) << 1;

return getSum(sum, carry);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.