打印二进制递归算法
printbinary recursive algorithm
我无法理解这个简单的递归函数是如何工作的：
void printBinary(const int& n)
{
if(n < 2)
{
cout << n;
}
else
{
printBinary(n / 2);
printBinary(n % 2);
}
}
我知道它与 n / 2 "chopping" 二进制表示的最后一位和 n % 2 产生二进制表示的最后一位有关，但是当我递归地跟踪这段代码时就像魔术一样。我想不出一个简单的逻辑解释。
编辑：
This 是对该算法的一个很好的解释，并引导我将我的问题改写为：为什么 n % 2 或十进制数的余数会给出该数字的二进制数字。这背后的逻辑是什么？
对于递归算法，我总是发现在带有缩进的文本文件中快速写出一个小示例以显示递归级别很有帮助：
f(42)
f(21)
f(10)
f(5)
f(2)
f(1) - 1
f(0) - 0
f(1) - 1
f(0) - 0
f(1) - 1
f(0) - 0
这是二叉树中的等效树，可能会有所帮助：
f(101010b)
f(10101b)
f(1010b)
f(101b)
f(10b)
f(1b) - 1
f(0b) - 0
f(1b) - 1
f(0b) - 0
f(1b) - 1
f(0b) - 0
从这里你会看到，第一个递归调用（n/2）会一直除以2，直到找到最高有效位，递归的次数就是这个数答案中的位。在得到 1 或 0 之前，您可以将 42 除以 2？ 6次，所以答案总共有6位。
下一步不太明显。当您向下钻取到倒数第二个级别 - f(2) 或 f(10b) 时，您所做的就是确定两个最重要的数字。查看可能不那么令人困惑的十进制值。
f(1234)
f(123)
f(12)
f(1) - 1
f(2) - 2
f(3) - 3
f(4) - 4
当你一直除以 10 时，你总是有一些最高有效数字。当你到达最后两位数 (12) 时，第一个是 12/10，第二个是 12%10。回到一个级别，(123)，你已经递归地处理了前两个最重要的数字 f(12) 现在你 运行 f(3) 在小数情况下将是的一部分基本情况 (n <10).
希望对您有所帮助
我无法理解这个简单的递归函数是如何工作的：
void printBinary(const int& n)
{
if(n < 2)
{
cout << n;
}
else
{
printBinary(n / 2);
printBinary(n % 2);
}
}
我知道它与 n / 2 "chopping" 二进制表示的最后一位和 n % 2 产生二进制表示的最后一位有关，但是当我递归地跟踪这段代码时就像魔术一样。我想不出一个简单的逻辑解释。
编辑： This 是对该算法的一个很好的解释，并引导我将我的问题改写为：为什么 n % 2 或十进制数的余数会给出该数字的二进制数字。这背后的逻辑是什么？
对于递归算法，我总是发现在带有缩进的文本文件中快速写出一个小示例以显示递归级别很有帮助：
f(42)
f(21)
f(10)
f(5)
f(2)
f(1) - 1
f(0) - 0
f(1) - 1
f(0) - 0
f(1) - 1
f(0) - 0
这是二叉树中的等效树，可能会有所帮助：
f(101010b)
f(10101b)
f(1010b)
f(101b)
f(10b)
f(1b) - 1
f(0b) - 0
f(1b) - 1
f(0b) - 0
f(1b) - 1
f(0b) - 0
从这里你会看到，第一个递归调用（n/2）会一直除以2，直到找到最高有效位，递归的次数就是这个数答案中的位。在得到 1 或 0 之前，您可以将 42 除以 2？ 6次，所以答案总共有6位。
下一步不太明显。当您向下钻取到倒数第二个级别 - f(2) 或 f(10b) 时，您所做的就是确定两个最重要的数字。查看可能不那么令人困惑的十进制值。
f(1234)
f(123)
f(12)
f(1) - 1
f(2) - 2
f(3) - 3
f(4) - 4
当你一直除以 10 时，你总是有一些最高有效数字。当你到达最后两位数 (12) 时，第一个是 12/10，第二个是 12%10。回到一个级别，(123)，你已经递归地处理了前两个最重要的数字 f(12) 现在你 运行 f(3) 在小数情况下将是的一部分基本情况 (n <10).
希望对您有所帮助