recursive function matlab decimal to binary conversion

Question

I have a function that converts a decimal number to binary but i need to make the function recursive. I don't know how to make this function call itself. Any help will be very appreciated.

This is my function :

function bin = myBinary (dec_nr)
i = 1; 
q = floor(dec_nr/2); %this is the quotient, the "floor" function is used to   round down 
r = rem(dec_nr, 2); % the "rem" function is used to get the remainder which will become the first binary value 
bin(i) = num2str(r(i)); % the remainder is converted and stored as a string 

while 2 <= q
dec_nr = q;
i = i + 1;
q = floor(dec_nr/2);
r = rem(dec_nr, 2);
bin(i) = num2str(r);
end
bin(i + 1) = num2str(q);
bin = fliplr(bin);
save myBinary

Thank you in advance!

Answer 1

That's pretty simple to do. I would implement this using something called tail recursion. Remember the algorithm for converting a decimal number (assuming unsigned) into binary.

1. Declare a number you want to convert.
2. Initially declare an output to be empty.

3. Until the number is 0...

   a. Take the number and divide this by 2

   b. If there is a remainder, then attach a bit of 1 from the left, so output <- [1 output]. Else, attach a 0, so output <- [0 output].

output will contain the binary representation of your number.

With recursion, there are two cases you must consider: The base case, where the algorithm stops and gives you a known output, and a recursive case that tells you that you need to keep going, and you call the function again with modified inputs.

As such, you can very easily achieve what you want above by tail recursion by providing a helper function that takes in the input number at a given state (basically the number after being divided by 2 for a number of times) and a binary string that gives you the current state of binary string construction as you're going through and determining each bit.

You would repeatedly call this function and taking the input number and dividing it by 2 until you get a result of 0. You would start by calling the function with the original input number, and an empty string. Make sure that when you send the input number back into the function for the recursive case, you need to truncate any decimal values that result, so you would take the floor.

Therefore, a possible function is very simply:

function bin = bin2dec_recursive(in)

    %// Recursive helper
    function [out] = recursive_helper(in_number, binstr)
        %// Base case
        if in_number == 0
            out = binstr; %// Just return the current binary string
        %// Recursive case
        else
            %// Recurse - Integer divide input number and concatenate string
            out = recursive_helper(floor(in_number/2), [num2str(mod(in_number,2)) binstr]);
        end
    end

    %// call recursive helper
    bin = recursive_helper(in, '');
end

What's key is this statement right here:

out = recursive_helper(floor(in_number/2), [num2str(mod(in_number,2)) binstr]);

When we hit the recursive case, we need to call the function again by dividing the input number by 2 and the input binary string is the current string, but we add either a 0 or 1 to the left of the string. We convert the number to a string by num2str.

If you desire to have a double array of single digits, simply remove the num2str call inside the recursive case, and replace '' with [] when you're calling the recursive helper function for the first time at the last line of code above.

---

With this, here are some examples of it working:

>> bin2dec_recursive(3)

ans =

11

>> bin2dec_recursive(5)

ans =

101

>> bin2dec_recursive(9)

ans =

1001

>> bin2dec_recursive(127)

ans =

1111111

>> bin2dec_recursive(200)

ans =

11001000

---

Minor Note

Be advised that the recursion limit for MATLAB is 500 calls. Therefore, with recursion, you can only compute binary numbers that are up to a maximum of 500 bits, so this means that the maximum decimal number you can put into the above function is approximately 2⁵⁰⁰ - 1. Anything more will give you an error saying that MATLAB has reached its recursion limit.