c++ - 打印二进制递归算法

Question

我无法理解这个简单的递归函数是如何工作的:

void printBinary(const int& n)
{
    if(n < 2)
    {
        cout << n;
    }
    else
    {
        printBinary(n / 2);
        printBinary(n % 2);
    }
}

我知道它与 n/2 “砍掉”二进制表示的最后一位和 n % 2 产生二进制表示的最后一位有关，但是当我递归地跟踪这段代码时，它看起来就像魔术.我想不出一个简单的合乎逻辑的解释。

编辑: This是对该算法的一个很好的解释，并引导我将我的问题改写为:为什么 n % 2 或十进制数的余数会为您提供该数字的二进制数字。这背后的逻辑是什么？

Answer 1

对于递归算法，我总是发现在带有缩进的文本文件中快速写出一个小示例以显示递归级别会很有帮助:

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

希望对你有帮助