有人可以解释在查找所有子集时递归是如何工作的吗? [英] Can someone explain how recursion works when finding all subsets?

问题描述

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

I cannot, for the life of me, picture recursion and what it's doing. I struggle with this a lot. From the Competitive Programmer's Handbook, I uncovered the following snippet of code in C++ as a solution to the following problem:

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

Consider the problem of generating all subsets of a set of n elements. For example, the subsets of {0,1,2} are ;, {0}, {1}, {2}, {0,1}, {0,2}, {1,2} and {0,1,2}.

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

An elegant way to go through all subsets of a set is to use recursion. The following function search generates the subsets of the set {0,1,...,n − 1}. The function maintains a vector subset that will contain the elements of each subset. The search begins when the function is called with parameter 0.

当用参数k调用函数search时，它决定是否将元素 k 包含在子集中，以及两者中情况，然后用参数 k + 1 调用自身 但是，如果 k = n，则函数通知所有元素都已处理，并且有一个子集已生成.

When the function search is called with parameter k, it decides whether to include the element k in the subset or not, and in both cases, then calls itself with parameter k + 1 However, if k = n, the function notices that all elements have been processed and a subset has been generated.

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

当然，这个功能是有效的，我已经手工完成了大约 3 次，看看它是否完美无缺.但为什么?

So sure, this function works and I have done it about 3 times by hand to see that it does work flawlessly. But why?

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

Short of memorizing all recursive solutions for all problems I will never be able to come up with this kind of solution. What kind of abstraction is being made here? What is the more general concept that is being used here?

我一直在努力解决递归问题，因此感谢您的任何帮助.谢谢.

I've always struggled with recursion so any help is appreciated. Thank you.

推荐答案

对于每个 k 我们只是递归地调用 search(k+1) .一次在你的集合中有 k 的值，一次没有它.

For each k < n we simply call search(k+1) recursively. once with the value k inside your set and once without it.

    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，递归终止.

Once we reach n==k the recursion is terminated.

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

Imagine a binary tree of depth n, where each level represents the current value and the two branches, the decision if the value goes into your final set or not. The leaves represent all final sets.

因此给定 n=3 并从 k=0 开始，您得到:

So given n=3 and starting with k=0 you get:

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 在他的评论中巧妙地指出的那样，递归使用了以下事实:

As john smartly pointed out in his comment, the recursion uses the fact that:

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

all_subsets(a1,a2,...,an) == all_subsets(a2,...,an) U {a1, all_subsets(a2,...,an)} where U is the set union operator.

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

Many other mathematical definitions will translate into recursive calls naturally.

这篇关于有人可以解释在查找所有子集时递归是如何工作的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！