Binary to Gray code using recursion

Given the Binary code of a number as a decimal number, we need to convert this into its equivalent Gray Code. Assume that the binary number is in the range of integers. For the larger value, we can take a binary number as string.

Note: In Gray Code, two consecutive bits differ by exactly one bit. The most significant bit (MSB) of the Gray Code is always the same as the MSB of the binary number.

Examples: 

Input: 1001 
Output: 1101
Explanation: The Gray Code for binary 1001 is 1101.

Input: 11
Output: 10
Explanation: The Gray Code for binary 11 is 10.

Approach [Using Recursion]

The idea is based on the property that each bit of the Gray Code can be obtained by performing XOR between the current binary bit and the previous binary bit.

To generate the Gray Code, the binary number is processed recursively from right to left. In each step, the last binary digit is compared with the second last digit. If both digits are different, 1 is appended to the Gray Code; otherwise, 0 is appended. The function is then recursively called on the remaining digits (n / 10).

The result of the recursive call is multiplied by 10 to shift the digits to the left, and the new Gray Code bit is added. The base case occurs when n == 0, where the function returns 0.

#include <cstdio>
using namespace std;

int binary_to_gray(int n)
{
    if (!n)
        return 0;

    // Taking last digit
    int a = n % 10;

    // Taking second last digit
    int b = (n / 10) % 10;

    // If last digit are opposite bits
    if ((a && !b) || (!a && b))
        return (1 + 10 * binary_to_gray(n / 10));

    // If last two bits are same
    return (10 * binary_to_gray(n / 10));
}

int main()
{
    int binary_number = 1011101;

    printf("%d", binary_to_gray(binary_number));
    return 0;
}

import static java.lang.StrictMath.pow;
import java.util.Scanner;

class GfG {

    int binary_to_gray(int n, int i)
    {
        int a, b;
        int result = 0;
        if (n != 0) {
            // Taking last digit
            a = n % 10;

            n = n / 10;

            // Taking second last digit
            b = n % 10;

            if ((a & ~b) == 1 || (~a & b) == 1) {
                result = (int)(result + pow(10, i));
            }

            return binary_to_gray(n, ++i) + result;
        }
        return 0;
    }

    public static void main(String[] args)
    {
        int binary_number;
        int result = 0;
        binary_number = 1011101;

        bin_gray obj = new bin_gray();
        result = obj.binary_to_gray(binary_number, 0);

        System.out.print(result);
    }
}

//

def binary_to_gray(n):
    if not (n):
        return 0

    # Taking last digit
    a = n % 10

    # Taking second last digit
    b = int(n / 10) % 10

    # If last digit are opposite bits
    if (a and not (b)) or (not (a) and b):
        return (1 + 10 * binary_to_gray(int(n / 10)))

    # If last two bits are same
    return (10 * binary_to_gray(int(n / 10)))

if __name__ == "__main__":
    binary_number = 1011101
    print(binary_to_gray(binary_number), end='')

using System;

class GfG {

    static int binary_to_gray(int n, int i)
    {
        int a, b;
        int result = 0;
        if (n != 0) {

            // Taking last digit
            a = n % 10;

            n = n / 10;

            // Taking second last digit
            b = n % 10;

            if ((a & ~b) == 1 || (~a & b) == 1) {
                result = (int)(result + Math.Pow(10, i));
            }

            return binary_to_gray(n, ++i) + result;
        }

        return 0;
    }

    public static void Main()
    {
        int binary_number;
        binary_number = 1011101;

        Console.WriteLine(binary_to_gray(binary_number, 0));
    }
}

function binary_to_gray(n, i)
{
    let a, b;
    let result = 0;
    if (n != 0) {
        // Taking last digit
        a = n % 10;

        n = n / 10;

        // Taking second last digit
        b = n % 10;

        if ((a & ~b) == 1 || (~a & b) == 1) {
            result = (result + Math.pow(10, i));
        }

        return binary_to_gray(n, ++i) + result;
    }
    return 0;
}

// Driver code
let binary_number;
let result = 0;
binary_number = 1011101;

result = binary_to_gray(binary_number, 0);

console.log(result);

1110011

Time Complexity: O(log₁₀(n)), as the function processes one digit in each recursive call.
Auxiliary Space: O(log₁₀(n)), due to recursive call stack for each digit.