3-line dec-bin conversion function needs explanation

Question

I want to be able to accurately explain the following function.

void ToBin(int n){ if (n>1) ToBin( n/2 ); printf( "%d", n%2 ); } 

For instance:
If I introduce 7 , then what happens (the behavior of the function) to convert to binary 111 .

Please, I want a step-by-step explanation to understand.

---

Edit
The same function, but prints the result more clearly.

 void ToBin( int n ){ printf("%d/2= %d -> %d\n", n, n/2 ,n%2); if (n>1) ToBin( n/2 ); } 

Answer 1

C 7 in particular:

Firstly, n = 7, so n> 1. Thus, ToBin is again called on n / 2 = 3.

Now n = 3, so n> 1. Thus, ToBin is again called on n / 2 = 1.

Now n = 1, so n is not more than 1. Thus, 1% 2 = 1 is printed, and control passes to the previous frame.

It prints n = 3 and 3% 2 = 1, with the control coming back again.

It displays n = 7 and 7% 2 = 1, and since the function is left and there are no more ToBin frames, control returns to the function, which was originally called ToBin.

In general, this function works as follows:

The binary expression of a number is the binary expression of half half of that number, with the least significant bit of the original number being added.

Thus, the function repeatedly receives the binary expression half a half of the input until this value has one bit. Then this bit, which is the most significant bit of the number, is printed, and then, so that each bit is in decreasing order of value.

Answer 2

This is a recursive function call. n%2 basically just beats the last bit (binary representation) of an integer. (2, because binary is base 2, so two base numbers are possible). n/2 removes the least significant bit (integer division) and passes it to the next level of recursion.

Therefore, each recursion level cuts out the least significant bit of an integer, which is transmitted until an integer of 1 is at a certain level. If it is 1, then if fails and a more recursive call is not made. Now recursion is back. First, printf executes the last recursive call, which will print the least significant bit of the integer that it passed to the caller. Therefore, at the k level, k ^ th bits are mainly printed. Since at level k th, the least significant bits of k-1 were deleted along the chain of recursive function calls, and a call at level k has an integer with k-1 least significant bits. Thus, at each level, printf prints the LSB of the integer that it was passed until the recursion returns to the top.

Here is a graphical representation. for n = 10 . Then the binary code n is 1010 . Try to draw such diagrams with different values ​​yourself in order to better understand.

  ToBin (10 = 1010) print 10%2 = 0 | ^ call ToBin (10/2) | | | V | ToBin (5 = 101) print 5%2 = 1 | ^ call ToBin (5/2) | | | V | Tobin (2 = 10) print 2%2 = 0 | ^ call ToBin (2/2) | | | V | ToBin (1 = 1) print 1%2 = 1 | ^ if condition fails, | | roll back. | | | | | +------>------>------>------+ 

Answer 3

 order call print 1 ToBin(7) 1 ↓ ↑ 2 ToBin(3) 1 ↓ ↑ 3 ToBin(1) → 1 

What is Recursion

Maybe you should find this recursion equation.

Answer 4

To find the representation of base 2, we look for bits b0...bn such that

 n = bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0 

Now we will focus on finding b0, b1, ..., bn . note that

 (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) % 2 = b0 

because b0 * 2^0 % 2 = b0 and bj * 2^j % 2 = 0 when j >= 1 with 2^j % 2 = 0 if j >= 1 . Thus,

  n = bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0 => n % 2 = (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) % 2 = b0 

we found that b0 = n % 2 . This key fact is number one .

Now divide by 2:

 n / 2 = (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) = bn * 2^(n - 1) + b_(n - 1) * 2^(n - 2) + ... + b1 * 2^1 

Now let me stop here. Let's take a close look at the binary representation for n / 2 . Note that it is exactly equal to the binary representation of n with only the last beaten off. it

  n = bn b_(n-1) ... b1 b0 n / 2 = b_n b_(n-1) ... b1 

This is a key fact number two .

So, let's collect what we learned.

• The binary representation of n is the binary representation of n / 2 with the last digit of the binary representation of n added. This is out of key fact number two .

• The last digit of the binary representation of n can be calculated by computing n % 2 . This is from the key fact number one .

All this is true, except for one case: when n = 0 . In this case, the binary representation of n is 0 . If we try to use the rule of dividing by 2 , we will never stop dividing by 2. So, we need a rule that catches when n = 0 .

So, to compute the binary representation of n , first compute the binary representation of n / 2 , then add the result n % 2 , but be sure to handle the case where n = 0 . Let it be written that in the code:

 // print binary representation of n void ToBin(int n) { if(n > 1) { // this is to handle zero! ToBin(n / 2); // this will print the binary representation of n } print(n % 2); // this will print the the last digit } 

Answer 5

enter 7 to

 call 1) 7>1 true ,call ToBin(7/2)=ToBin(3.5) , pending print(7%2)=1 call 2) 3>1 true ,call ToBin(3/2)=ToBin(1.5) , pending print(3%2)=1 call 3) 1>1 false ,dont call ToBin(1/2), print(1%2)=1 

 print 1 pop function activation record for call 3) pending print 1 pop function activation record for call 2) pending print 1 pop function activation record for call 1) So your output is 111 

Answer 6

Recursion can make it harder to understand than it could otherwise be. First, note that if we reorder the operators:

 void ToBin(int n){ printf( "%d", n%2 ); if (n>1) ToBin( n/2 ); } 

Now it will print the numbers in reverse order. This, of course, is not what you want, but now that the recursive call ends, it is easier to convert to iterative form:

 void ToBin(int n) { do { printf( "%d", n%2 ); n = n/2; } while(n > 1); } 

From this code you can see it:

• Prints a modulo number two.
• Divides the number by two.
• If the number is greater than 1, it is repeated.

We believe that taking into account the base-10 number, we can divide by 10. The rest and dividends are the least significant digit and the number shifted by one digit, respectively. This also works for binary: instead of dividing by 10, we split into two.

Essentially, then the algorithm is as follows:

• Print the least significant digit.
• Shift the number by one digit.
• If the number is more than one, repeat.

If you write this in recursive form and then change the recursion and printing, you print a number with numbers in order from most significant to least significant. Voila.

Answer 7

 ToBin(7) n=7 if(7>1) ToBin(7/2=3) call ToBin(3) { ToBin(3) n=3 if(3>1) ToBin(3/2=1) call ToBin(1) { ToBin(1) n=1 if(1>1) false print n%2=> 1%2= 1 } print n%2=> 3%2= 1 } print n%2=> 7%2= 1 

Answer 8

Its remainder from recursive printing (% operation) by dividing 2 as follows

ToBin() calls itself before an argument n is entered greater than 1

  2 | 7 ------ remainder /|\ 2 | 3 ---> 1 | down to top ------ | | 1 ---> 1 | --------------------> 

Answer 9

If n is 7, recursive calls at each level

  1.ToBin(7)--> 2. ToBin(3) --> 3. ToBin(1) 

Now the values ​​are returned, and in the first case it is 1, and 7% 2 is 1,

1 in the second case, when 3% 2 is 1, 1 in the third case, also 1% 2 is 1.

Therefore, 111 is the output <

Note. . Each recursive call has its own n in its stack, so n is 7 in the first call, 3 per second and 1 in the third call.

Answer 10

The ToBin function uses recursion (calling the function itself) and use this algorithm :

To convert from an integer digit base-10 to its base-2 (binary) equivalent, the number is divided by two, and the rest is the least significant. The result (integer) is again divided by two, its remainder is the next least significant bit. This process is repeated until the coefficient becomes equal to zero.