有人可以解释在查找所有子集时递归是如何工作的吗？

Question

对于我的一生，我无法描绘递归及其正在做什么。我为此很挣扎。在Competitive Programmer's Handbook 中，我发现了以下 C++ 代码片段作为以下问题的解决方案：

考虑生成一组 n 个元素的所有子集的问题。例如，{0,1,2} 的子集是 ;, {0}, {1}, {2}, {0,1}, {0,2}, {1,2} 和 {0,1 ,2}。

遍历集合的所有子集的一种优雅方法是使用递归。以下函数 search 生成集合 {0,1,...,n 的子集？1}。该函数维护一个向量子集，该子集将包含每个子集的元素。当使用参数 0 调用函数时，搜索开始。

当使用参数 k 调用函数 search 时，它决定是否将元素 k 包含在子集中，并且在这两种情况下，都使用参数 k + 1 调用自身 但是，如果 k = n，则函数注意到所有元素已处理并已生成子集。

void search(int k) {
    if (k == n) {
        // process subset
    } else {
        search(k+1);
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
    }
}

可以肯定，此功能有效，我已经手动完成了大约 3 次，以查看它是否完美无缺。但为什么？

如果没有记住所有问题的所有递归解决方案，我将永远无法想出这种解决方案。这里进行了什么样的抽象？这里使用的更一般的概念是什么？

我一直在与递归作斗争，所以任何帮助表示赞赏。谢谢你。

Answer 1

对于每个k < n我们简单地search(k+1)递归调用。一次在您的集合中使用值k，一次没有它。

    search(k+1); // call search (k+1) with k NOT inside the set
    subset.push_back(k); // puts the value k inside the set
    search(k+1); // call search (k+1) with k inside the set
    subset.pop_back(); // removes the value k from the set

一旦我们达到n==k递归终止。

想象一个深度为 n 的二叉树，其中每个级别代表当前值和两个分支，决定该值是否进入您的最终集合。叶子代表所有最终集。

所以给定n=3并从k=0开始，你得到：

search(0); 
-> search(1); // with 0 in
->-> search(2); // with 0 in AND 1 in
->->-> search (3); // with 0 in AND 1 in AND 2 in. terminates with (0,1,2)
->->-> search (3); // with 0 in AND 1 in AND 2 not in. terminates with (0,1)
->-> search(2); // with 0 in AND 1 not in
->->-> search (3); // with 0 in AND 1 not in AND 2 in. terminates with  (0,2)
->->-> search (3); // with 0 in AND 1 not in AND 2 not in. terminates with  (0)
-> search(1); // with 0 not in
->-> search(2); // with 0 not in AND 1 in
->->-> search (3); // with 0 not in AND 1 in AND 2 in. terminates with  (1,2)
->->-> search (3); // with 0 not in AND 1 in AND 2 not in. terminates with  (1)
->-> search(2); // with 0 not in AND 1 not in
->->-> search (3); // with 0 not in AND 1 not in AND 2 in. terminates with  (2)
->->-> search (3); // with 0 not in AND 1 not in AND 2 not in. terminates with  ()

正如约翰在他的评论中巧妙地指出的那样，递归使用了以下事实：

all_subsets(a1,a2,...,an) == all_subsets(a2,...,an) U {a1, all_subsets(a2,...,an)}其中U是集合联合运算符。

许多其他数学定义将自然地转化为递归调用。