Understanding recursion for decimal to binary conversion

Hi everyone I hope you are well.

I am trying to convert decimal integers to binary but I am not allowed to use a built in matlab fucntion that does this. I have code that is suposed to do it but I am struggaling to understand the logic behind the code (which I will show below). I dont understand the general logic behind the code, nor how to approach recursion questions that arent reliativelly simple. In this code especially I am unsure as to why one uses a while loop, a floor command and why there is an empty bin_str="". Please if someone could help me with these questions I would really appreciate it. Thanks very much and I hope you have a good day :)

Here is the code.

function [bin_str]=d2b_convert(n)
if n==0
    bin_str='0';
    return;
end
bin_str='';
while n>0
    bin_str=[num2str(mod(n,2)) bin_str];
    n=floor(n/2);
end
end

[Chuguang Pan]

@Kyle. There is a buildin function dec2bin

[Walter Roberson]

@Chuguang Pan

@Kyle specifically said, "I am not allowed to use a built in matlab function that does this"

Answer 1

[David Goodmanson]

Hi Kyle, here is an attempt, hope it helps.

As Walter has noted, this is not a recursion since the function does not call a previous version of itself. Instead it's iteration with a defined stopping point.

First of all bin_str is a string that gets bits appended to it on the left. When you append for the first time, Matlab has to know that bin_str is even a variable in order to be able to append to it at all. bin_str = ' ' just says that bin_str does exist as a variable but so far it doesn't contain anything.

As you know a binary number has the form

n = .... c3 2^3 + c2 2^2 + c1 2^1 + c0 2^0

where each of the binary bits c are either 0 or 1. r = mod(n,2), the remainder of n divided by 2, is 0 or 1 as n is even or odd. That's the first bit, r = c0, which you enter into bin_str.

Now if you subtract r from n you get an even number. The first bit r = c0 is handled, and if you rearrange the eqn above you get

new n = (n-c0)/2 = .... c3 2^2 + c2 2^1 + c1 2^0

Here c1 is the smallest bit and you have the same situation all over again. Apply the same process, appending bits to the left of bin_str, until it reaches an end, n=0 at which point the condition ' while n>0 ' stops the process.

If r = 0 or 1, then floor(n/2) is the same thing as (n-r)/2 but probably not as clear.

I think the best possible way to learn this is to sit down and do the algorithm by hand, say for n = 21 or the like.

start with n and an empty bin_str

a) divide n by 2, find the remainder = r

b) append r to the left of bin_str

c) find new n = (n-r)/2

d) iterate a)b)c)d) until n = 0

For verification you can uncomment some of the lines in the code and see what happens along the way, but I think it's important to run it out first before the computer does so.

Answer 2

[Walter Roberson]

The posted code has no recursion.

In order for code to have recursion, there it must contain a chain of calls that end up calling the function itself again. (Most often, the function calls itself again directly, but it is legal for there to be a chain of calls instead of a direct call.)

In order for recursion to work, there must be at least one path through the code that calculates a result directly instead of calling the same function again.

In order for recursion to work, there must be tests (even if implied) done before the function calls itself.

Typically, in order for recusion to work, the amount of work to be done by subsequent calls must in some respect be "smaller" than the work to be done in the current call. However, this is not strictly theoretically necessary, as long as it can be proven that the chain of calls will eventually end.

function chain_of_values = collatz(N)
   if N < 1 || N ~= fix(N) || isinf(N)
       error('collatz(%g) not defined', N)
   elseif N == 1
       chain_of_values = N;
   elseif mod(N,2) == 0
       chain_of_values = [N, collatz(N/2)];
   else
       chain_of_values = [N, collatz(N*3+1)];
   end
end

This code has the form of recursion... but it is completely unknown whether the Collatz Conjecture always iterates to 1. The Collatz Conjecture iterates to 1 for every value that has been tested so far -- but "so far" is not a proof. If this code were to be applied to a value that did not iterate to 1, then this code would execute indefinitely (until it hit the recursion limit), even if it happened to encounter a different cycle.