如何用递归实现n次抛硬币的样本空间生成（支持Python/C）

Python 实现 #

递归方法 #

递归核心逻辑：n次抛硬币的样本空间，等于在n-1次的每个结果后分别追加'H'和'T'。基线条件为n=1时，返回单个硬币的两种结果。

def coin_flip_samples(n):
    if n == 1:
        return [['H'], ['T']]
    prev_samples = coin_flip_samples(n - 1)
    new_samples = []
    for sample in prev_samples:
        new_samples.append(sample + ['H'])
        new_samples.append(sample + ['T'])
    return new_samples

# 示例：生成3次抛硬币的样本空间
n = 3
for sample in coin_flip_samples(n):
    print(sample)

非递归方法（笛卡尔积） #

利用Python标准库itertools.product直接生成笛卡尔积，简洁高效：

import itertools

def coin_flip_samples_iter(n):
    return [list(item) for item in itertools.product(['H', 'T'], repeat=n)]

# 示例调用
n = 3
for sample in coin_flip_samples_iter(n):
    print(sample)

C语言实现 #

递归方法 #

通过递归逐位构建每个样本，达到n位时输出结果：

#include <stdio.h>
#include <stdlib.h>

void generate_samples(int n, char *current, int pos) {
    if (pos == n) {
        printf("[");
        for (int i = 0; i < n; i++) {
            if (i > 0) printf(", ");
            printf("'%c'", current[i]);
        }
        printf("]\n");
        return;
    }
    current[pos] = 'H';
    generate_samples(n, current, pos + 1);
    current[pos] = 'T';
    generate_samples(n, current, pos + 1);
}

int main() {
    int n = 3;
    char *current = (char *)malloc(n * sizeof(char));
    if (!current) {
        printf("内存分配失败\n");
        return 1;
    }
    generate_samples(n, current, 0);
    free(current);
    return 0;
}

非递归方法（二进制映射） #

利用0到2^n-1的二进制数每一位对应硬币结果（0→'H'，1→'T'），迭代生成所有样本：

#include <stdio.h>
#include <math.h>

int main() {
    int n = 3;
    int total = (int)pow(2, n);
    for (int i = 0; i < total; i++) {
        printf("[");
        for (int j = n - 1; j >= 0; j--) {
            if (j != n - 1) printf(", ");
            char c = ((i >> j) & 1) ? 'T' : 'H';
            printf("'%c'", c);
        }
        printf("]\n");
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Prateek Sharma