understanding recursive decimal to binary code?

问题:

I'm working on a program that can convert number to its binary form.

With help, I was able to get this, and it seems to work but I just don't understand how. I guess the best way to do this is to try to explain how I think this is working and someone can correct me.

I have a function that has an if statement that says if n divided by 2 isn't equal to 0 then divide n by 2. Then it prints the remainder if n /2 so either 1 or 0.

The main function just runs the function with whatever number I give it, in this case 456.

But how does the program know to run the function multiple times to get the entire binary form?

I feel like this isn't that complicated but I'm not getting it.

#include <stdio.h>

void ConvertToBinary(int n)
{
    if (n / 2 != 0) {
        ConvertToBinary(n / 2);
    }
    printf("%d", n % 2);
}

int main (){
    ConvertToBinary (456);
    return 0;
}

回答1:

The function ConvertToBinary is recursive, meaning it calls itself. At some point the function needs to know when to stop calling itself. This is called the base case.

On the first call to this function, n=456. In this case n/2 != 0 is true, so the function calls itself, this time with 228. It keeps calling itself until it gets passed a value where n/2 != 0 is false, which is the base case. The innermost call to the function then prints n % 2 and returns. The next innermost call also prints n % 2 for its value of n, and so on up the call stack.

So the function calls look something like this:

ConvertToBinary(456)
    ConvertToBinary(456/2=228)
        ConvertToBinary(228/2=114)
            ConvertToBinary(114/2=57)
                ConvertToBinary(57/2=28)
                    ConvertToBinary(28/2=14)
                        ConvertToBinary(14/2=7)
                            ConvertToBinary(7/2=3)
                                ConvertToBinary(3/2=1)
                                    print 1%2=1
                                print 3%2=1
                            print 7%2=1
                        print 14%2=0
                    print 28%2=0
                print 57%2=1
            print 114%2=0
        print 228%2=0
    print 456%2=0

Result:

111001000

回答2:

Step through it line by line on a piece of lined paper. Use indention as you make recursive calls, then unindent as you return. Place the output in the right column of your paper.

I would start with simple numbers like 1, 4, 7, 10, then try 456.

回答3:

This is my first answer here but I'll try and explain as best I can. This is an example of recursion (Google that) which is a powerful tool for solving certain kinds of problems. The trick is that the method calls itself, so tracing it through (with a smaller example):

1st call n = 13 call ConvertToBinary with 13 / 2 = 6

2nd call n = 6; call ConvertToBinary with 6 / 2 = 3

3rd call n = 3 call ConvertToBinary with 3 / 2 = 1

4th call n = 1 1 / 2 = 0 so continue through! print 1 % 2 = 1 method exits and returns to the 3rd call

3rd call again print 3 % 2 = 1 method exits and returns to the 2nd call

2nd call again print 6 % 2 = 0 method exits and returns to the 1st call

1st call again print 13 % 2 = 1 and done!

Now we have 1101 which is 13 in binary,

回答4:

#include <stdio.h>

void ConvertToBinary(int n)
{

 // is the number passed in 2 or greater? If so, print out the smaller binary digits first. 
 if (n / 2 != 0) {  

 // this is a recursive call. It won't return until all the smaller binary digits have been printed. 
 ConvertToBinary(n / 2);
}

 // all the smaller digits have been printed, time to print out the current binary digit. 
 printf("%d", n % 2);
}

int main (){
ConvertToBinary (456);
return 0;
}