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

Question

我无论如何也无法想象递归及其作用。我对此很困惑。在竞技程序员手册中，我发现以下C++代码片段是解决以下问题的解决方案：

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

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

当函数search以参数k被调用时，它决定是否将元素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();
    }
}

所以，确实，这个函数是有效的，我亲手测试了三次并且它完美地工作了。但是为什么呢？

除非我能记住所有递归问题的解决方案，否则我永远无法想出这种解决方案。在这里做了什么样的抽象化？使用了哪些更一般的概念？

我一直很难理解递归，所以任何帮助都将不胜感激。谢谢。

- herophant

---

@SilvioMayolo 抱歉，这是引用自书中的内容。基本上它想表达的是只有一个向量。但是如果 k == n 成立，那么我们可以对这个向量（以及每个子集的元素）进行任何操作。我认为不应该过多地解读它。 - herophant

@john 好的。我做过像Scheme这样的Lisp相关事情，所以我知道你在用car和cdr/ first和rest表达什么......但是对于我来说，将这个简单的问题抽象化到这里很困难。这段代码对我来说仍然是神秘的，这就是为什么我要求更多细节的原因。 - herophant

递归很简单；它只是一个函数调用另一个函数 - 只不过它调用的函数恰好是它自己。但这与它调用其他函数没有什么不同。 - Jesper Juhl

@herophant，这段代码基本上利用了这个事实：所有子集(a1,a2,...,an) == 所有子集(a2,...,an) U {a1, 所有子集(a2,...,an)}，其中 U 是集合并运算符。这是一个递归定义，因为所有子集的定义是以它自己为基础定义的。现在，这段代码相当直接地对该定义进行了翻译。你不理解的问题是你看不出这个定义在数学上是正确的吗？还是你不明白这段代码如何捕捉这个定义的呢？ - john

@Chipster 我大概知道什么是递归，但在这个问题上应用起来有点困难。 - herophant

Answer 1

对于每个小于n的k，我们只需使用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  ()

正如john在他的评论中所指出的那样，递归使用以下事实：
all_subsets(a1,a2,...,an) == all_subsets(a2,...,an) U {a1, all_subsets(a2,...,an)} 其中U是集合并运算符。
许多其他数学定义也可以自然地转化为递归调用。

- oo_miguel

---

追踪不是反向的吗？我们在第一个位置不包含0的情况下进行调用，对吧？为什么第一次调用中它说0在里面？ - herophant

@herophant：是的，完全正确。抱歉，我把顺序搞错了...看来你理解了 ;) - oo_miguel

@herophant：特别是当你处理无限列表时，从开始/底部开始可能更好。你可以将从无限列表中“取n个元素”看作：take n {a1,a2,a3...} = take (n-1) {a2,a3,...} 等等... - oo_miguel

@herophant：每次调用函数时，参数和返回地址都会被放在堆栈上，因此如果您的递归嵌套得太深，可能会导致堆栈溢出。这可以通过尾递归来解决，这是另一个讨论的主题；一旦递归达到最深层次，它将调用您的“//处理子集”代码并返回到上一级（永远不会再返回）。 - oo_miguel

@herophant：push_back()和pop_back()会在每个级别上为较高级别已经进行的所有push_back()和pop_back()的组合执行！ - oo_miguel

Answer 2

我认为你缺乏的是可视化。所以我建议你访问像algorithm-visualizer.org，pythontutor.com这样的网站。

你可以将这段代码片段here粘贴并逐行运行，以便了解代码流程如何工作。

#include <bits/stdc++.h>
using namespace std;

void subsetsUtil(vector<int>& A, vector<vector<int> >& res, vector<int>& subset, int index) {
    res.push_back(subset);
    for (int i = index; i < A.size(); i++) {
        subset.push_back(A[i]);
        subsetsUtil(A, res, subset, i + 1);
    }
    return;
}

vector<vector<int> > subsets(vector<int>& A) {
    vector<int> subset;
    vector<vector<int> > res;
    int index = 0;
    subsetsUtil(A, res, subset, index);
    return res;
}

int32_t main() {
    vector<int> array = { 1, 2, 3 };
    vector<vector<int> > res = subsets(array);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }
    return 0;
}

很好，你真的在努力学习。这将对你在竞赛编程中有很大帮助。希望这能帮到你。

- Aman Raj

Answer 3

这不仅是你的问题。每个初学递归的人都会面临这个问题。最重要的是可视化。字面上看起来很难。

如果您尝试通过将任何递归代码变得手工（使用笔和纸）来进行可视化，您将会发现“哦！它正在工作”。但是您应该知道，大多数递归都有一个递归关系。基于此，函数递归。同样，为了找到特定集合的所有子集，存在一个递归关系。如下所示...

通过取特定项+不取该项

在您的代码中，“取特定项”意味着“Push_back”，而“不取特定项”意味着“Pop_back”。就是这样。

可能性之一是不取任何项。我们称其为空集。 另一种可能性是取所有项目。这里是{0,1,2}。

从排列组合理论中，我们可以计算出子集的数量。即2ⁿ，其中n是项目数。这里n=3。因此，子集的数量将为2³=8。

对于0，可以选择保留或放弃，可能性=2
对于1，可以选择保留或放弃，可能性=2
对于2，可以选择保留或放弃，可能性=2

总的子集数为2*2*2 = 8（包括空集）。
如果不考虑空集，那么子集的总数将是8-1 = 7。

这就是你递归代码背后的理论。

- Kazi Ziaul Hassan