c - 可视化二叉树的递归

Question

编写一个递归函数，显示由 xs、0s 和 1s 组成的字符串表示的所有二进制(以 2 为基数)数字。 xs 代表可以是 0 或 1 的数字。 例如，字符串 xx 表示数字 00,01,10,11。

代码有效，但我很难想象中间步骤。有人可以帮我演练吗？

void get_first_x(char *line,char *line2,char *line3);
void display(char *line);
int main(int argc, const char * argv[]) {

    char line[256];
    printf("Binary number: ");
    scanf("%s",line);
    display(line);
    return 0;
}


void display(char *line){


    char line2[80];
    char line3[80];

    if(strchr(line,'x') == NULL)
    {
        printf("%s\n",line);
        return;
    }

   get_first_x(line,line2,line3);


    display(line2);

    display(line3);

  }

   void get_first_x(char* line,char* line2,char *line3) {

    char* check;

    check = strchr(line,'x');
    *check = '0';

    strcpy(line2,line);

    *check = '1';
    strcpy(line3,line);

}//replacement of x with 0 and 1. One argument produces 2 strings

Here's my take

1st call     display(xx)
2nd call       display(0x)
3rd call          display(00) { print statement/ return}
                     display(1x)
                        display(01) { print statement/return}
                          display(10) { print statement/return}
                           recursion exits
 Input: xx
 output: 00,01,10,11
 I'm not understanding something...here

Answer 1

你实现的是这个(伪代码):

display(line) {
  if no_x_in(line) {
     print(line)  // instance output and recursion stop 
  } 
  display(replace_first_x_with_0(line))  // recursive call
  display(replace_first_x_with_1(line))  // recursive call
}

• 如果 line 中的字符串不再包含 x 符号，您可以输出字符串并且您的递归下降可以停止。

• 如果不是，则问题实例从具有 n 倍 x 符号的 行 减少为两个较小的实例，每个有 n - 1 个 x 符号，

  • 用 0 符号替换 x 和
  • 一个用 1 符号替换了 x。

这导致每个递归调用。由于有限输入字符串中只有有限多个 x 符号，递归调用将在某个点停止，并且生成的调用树也是有限的。

对于您的示例，调用树是这样的:

display('xx') -> issues calls to display('0x') and display('1x')
|
+-> display('0x') -> issues calls to display('00') and display('01')
|   |
|   +-> display('00') -> output, stop
|   +-> display('01') -> output, stop
|
+-> display('1x') -> issues calls to display('10') and display('11')
    |
    +-> display('10') -> output, stop
    +-> display('11') -> output, stop