理解递归十进制到二进制代码？

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.

我有一个函数,它有一个if语句,表示如果n除以2不等于0则将n除以2.然后如果n / 2则为1或0,则打印余数。

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

main函数只运行我给它的任何数字的函数,在本例中为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;
}

4 个解决方案

#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.

ConvertToBinary函数是递归的,这意味着它自己调用。在某些时候,函数需要知道何时停止调用自身。这称为基本情况。

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.

在第一次调用此函数时,n = 456。在这种情况下,n / 2!= 0为真,所以函数调用自身,这次是228.它一直调用自身直到它传递一个值,其中n / 2!= 0为假,这是基本情况。对函数的最内部调用然后打印n%2并返回。下一个最里面的调用也会为n的值打印n%2,依此类推调用堆栈。

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.

我会从简单的数字开始,如1,4,7,10,然后尝试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

第一次调用n = 13调用ConvertToBinary,13/2 = 6

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

第二次通话n = 6;调用ConvertToBinary,6/2 = 3

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

第3次调用n = 3调用ConvertToBinary,其中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

第4个电话n = 1 1/2 = 0所以继续! print 1%2 = 1方法退出并返回第3个调用

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

再次打3次打印3%2 = 1方法退出并返回第2次调用

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

再次打电话打印6%2 = 0方法退出并返回第一个电话

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

第一次打电话打印13%2 = 1完成!

Now we have 1101 which is 13 in binary,

现在我们有1101,二进制是13,

#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;
}

#1