Different behaviour of recursion-based powerset in C and Python

Question

On trying to implement a recursion-based technique to find powerset of a list, there was different behaviour in the C and Python implementation. It was first tried in Python using pseudocode as follows

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)

This calls the sets up to N, starting from 2 by adding another element and not adding in another.

My c code is as follows

#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);
}

To avoid using a dynamic list, I've used a boolean array. The problematic code is probably the if block with n<N check. This code uses tabs to space between different levels of recursion to make debugging easier.

The same for 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 output

 []
        []
            []
                []
                [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 output

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

Answer 1

The difference is in these pieces of code:

Python:

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

C:

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

The issues:

1. The C code makes the selection in a different order, including n+1 for the second recursive call -- while the Python version does that for the first recursive call. This is not really a problem, but partly explains the difference in output.

2. More of a problem is that the C code does not set s[n+1] back to false after the second recursive call, which will (badly) impact the behaviour higher up the recursion tree. This is a bug that is not present in the Python code, where the selection of i+1 only exists during the recursive call, but doesn't continue to be selected after that recursive call has finished.

To fix the bug you could add the following statement after the second recursive call:

    s[n+1] = false;

But to make the output the same as for the Python code, also switch the order:

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