c 和 python 上基于递归的幂集的不同行为

Question

在尝试实现基于递归的技术来查找列表的幂集时，c 和 python 实现中存在不同的行为。 首先在Python中使用伪代码进行了尝试，如下

def(f, n):
  if n<N:
    f(s+[n+1], n+1)
    f(s, n+1)

  if n==N:
    # all elements end up here

f([], 1)

这将集合称为 N，从 2 开始，添加另一个元素而不添加其他元素。

我的c代码如下

#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#define u8 uint8_t


#define N 4
void f(bool *s, u8 n){


  printf("%*s", 4*n, "");
  printf("[");
  for(int i=2;i<=N;i++)
    if(s[i]) printf("%d ", i);
  printf("]\n");



  if(n<N){
    f(s, n+1);
    s[n+1] = true;
    f(s, n+1);
  }

  if(n==N){}

}

int main(){
  bool s[N+1] = {false};
  f(s, 1);
}

为了避免使用动态列表，我使用了布尔数组。有问题的代码可能是带有

n<N

检查的 if 块。此代码使用制表符在不同级别的递归之间留出空间，以便更轻松地进行调试

Python 也一样

N = 4
def f(s, n):
    print('\t'*n, s)
    if n<N:
        f(s+[n+1], n+1)
        f(s, n+1)
    if(n==N):
        pass
            

f([], 1)

C输出

 []
        []
            []
                []
                [4 ]
            [3 4 ]
                [3 4 ]
                [3 4 ]
        [2 3 4 ]
            [2 3 4 ]
                [2 3 4 ]
                [2 3 4 ]
            [2 3 4 ]
                [2 3 4 ]
                [2 3 4 ]

Python 输出

     []
         [2]
             [2, 3]
                 [2, 3, 4]
                 [2, 3]
             [2]
                 [2, 4]
                 [2]
         []
             [3]
                 [3, 4]
                 [3]
             []
                 [4]
                 []

Answer 1

区别在于这些代码：

Python：

    f(s + [n+1], n+1)
    f(s, n+1)

C：

    f(s, n+1);
    s[n+1] = true;
    f(s, n+1);

问题：

1. C 代码以不同的顺序进行选择，包括

   n+1

   用于第二次递归调用，而 Python 版本则针对第一个递归调用执行此操作。这并不是真正的问题，但部分解释了输出的差异。

2. 更多的问题是，C 代码在第二次递归调用后不会将

   s[n+1]

   设置回

   false

   ，这将（严重）影响递归树上层的行为。这是 Python 代码中不存在的错误，其中

   i+1

   的选择仅在递归调用期间存在，但在递归调用完成后不会继续被选择。

要修复该错误，您可以在第二次递归调用后添加以下语句：

    s[n+1] = false;

但要使输出与 Python 代码相同，还要切换顺序：

    s[n+1] = true;
    f(s, n+1);
    s[n+1] = false;
    f(s, n+1);