Recursion: Given two numbers, add them recursively

Problem Statement:

You are given 2 numbers.

You need to perform bitwise recursive addition of the 2 integers.

Example:

Input:

a = 20
b = 30

Output: 50

Solution Explanation:

XOR Operation (x ^ y): We will use this operation, that adds 2 numbers without considering carry.

AND Operation (x & y): We will use this operation, that identifies the carry bits. If both bits of x and y are 1.

Now for the solution, the function takes 2 parameters, the xor value and one more is the carry.

The recursion will stop once the carry will be 0.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;


int solution(int x, int y) {

    if (y == 0) {
        return x;
    }

    int carry = (x & y) << 1;
    return solution((x ^ y), carry);
}

int main() {
  
    int x = 10, y = 5;

    cout << solution(x, y);
    return 0; 
}

Output

15