recursion - 生成 ‘n’ 位的所有字符串。假设 A[0....n-1] 是一个大小为 n 的数组

Question

void binary(int n)
{
    if(n < 1)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1] = '0';
        binary(n-1);
        A[n-1] = '1';
        binary(n-1);
    }
}

任何人都可以解释 n = 的堆栈帧吗？ 2？我的意思是当 n = 2 , 我收到 00当我在做空跑时。但也有01我错过了。有人可以解释一下为这段代码生成了什么堆栈帧吗？

Answer 1

让我们试着理解代码。

if(n < 1)
    printf("%s\n",arr);
else
{
    arr[n-1] = '0';
    binary(n-1);
    arr[n-1] = '1';
    binary(n-1);
}

因为它是一个递归函数，所以我们将遵循向后的方法。例如让我们说 n = 1 ,

该方法被称为 binary(1);arr[n-1]设置为 ‘0’ (arr[1-1] = arr[0] = ‘0’)
现在我们打电话binary(0);自 (n<1)我们打印 arr (打印 0)

调用返回 arr[n-1] = ‘1’arr[1-1]设置为‘1’ (arr[1-1] = arr[0] = ‘1’)
现在我们打电话binary(0);自 (n<1)我们打印 arr (1 已打印)

因此，我们得到了 2 个输出尽可能位 0和 1 .

现在让我们假设 n = 2 ,

该方法被称为 binary(2)arr[2-1]设置为‘0’ (arr[2-1] = arr[1] = ‘0’)
现在我们打电话binary(1);从上面的解释我们知道binary(1)为 arr[0] 产生 0 和 1 的输出.
这里arr[1]设置为 0。所以我们得到 2 个输出(00 和 01)。

函数返回arr[n-1] = ‘1’arr[2-1]设置为 1 (arr[2-1] = arr[1] = ‘1’)
我们再次调用 binary(1);这次arr[1]被设置为“1”，因此我们得到了另外 2 个输出(10 和 11)。

我们在屏幕上总共有 4 个输出..(00, 01, 10, 11) 这些都是 2 位的字符串。

同样，您可以解决 n = 3.arr[2]设置为“0”和 binary(2)叫做。这产生 (000, 010, 100, 110)arr[2]然后设置为“1”和 binary(2)叫做。这会产生 (001, 011, 101, 111)。
这些都是 3 位的字符串。

我希望这个方法能说清楚。也请随时提出任何其他问题。