递归思维的算法是什么? (在特定示例中) [英] What is the algorithm of thinking recursive? (on the specific example)
问题描述
我只是无法绕过递归.我了解所有概念(将解决方案分解为较小的案例)，并且一遍又一遍地阅读后，我才能理解解决方案.但是我永远无法弄清楚如何使用递归来解决问题.有没有系统的方法来提出递归解决方案?
I just can't wrap my head around recursion. I understand all of the concepts (breaking solution into smaller cases) and I can understand solutions after I read them over and over again. But I can never figure out how to use recursion to solve a problem. Is there any systematic way to come up with a recursive solution?
有人尝试解决以下递归问题时，请给我解释一下他们的思考过程:使用递归返回字符串的所有排列" .
Can someone please explain to me their thought process when they try to solve the following recursive problem: "Return all permutations of a string using recursion".
这是我解决这个问题的思考过程的一个例子.
Here is an example of my thought process to solve this problem.
- 检查字符串长度是否等于2.如果是，则交换值(基本情况)
- 否则:对于每个第一个值，返回第一个值+递归(不包含第一个值的字符串)
有人可以给我一些提示来改变我的思维过程或以更好的方式考虑递归问题，这样我就可以解决递归问题而不必查找答案.
Can somebody please give me some tips to change my thought process or to think of recursion in a better way so I can solve recursive problems without just looking up the answers.
编辑:这是我编写此问题的另一种解决方案的过程.
EDIT: Here is my thought process in coding another solution to this problem.
- 基本情况是字符串长度= 0
- 如果不是基本情况，则对于字符串的每个第一个字母，将第一个字母插入到字符串的每个排列的每个位置而没有第一个字母
- Ex:字符串是"abc"，第一个字母是a，因此请在"bc"排列的每个位置插入a. [bc，cb] => [abc，bac，bca，acb，cab，cba]
伪代码
permutation(String s, List l) {
if(s.length() == 0) {
return list;
}
else {
String a = s.firstLetter();
l = permutation(s.substring(1, s.length) , l)
for(int i = 0; i < s.length(); i++) {
// loop that iterates through list of permutations
// that have been "solved"
for(int j=0; j < l.size(); j++) {
// loop that iterates through all positions of every
// permutation and inserts the first letter
String permutation Stringbuilder(l[i]).insert(a, j);
// insert the first letter at every position in the
// single permutation l[i]
l.add(permutation);
}
}
}
}
推荐答案
思考过程:
给出 :一个字符串.
Given: a string.
目标: 以构建包含所有排列的列表.
The goal: to construct a list containing all of its permutations.
涉及的类型 :字符串的排列是字符串的列表(集合)，其中每个字符串都是输入字符串的某些排列.字符串是一个字符列表(序列).
Types involved: permutations of a string is a list (collection) of strings where each is some permutation of the input string. String is a list (sequence) of characters.
分析 :字符串可以分为 head 元素(字符)和 rest 元素，如果不为空.嗯， if 我们知道如何找到 rest 的排列，我们可以找到整个 if 的排列，我们找到了组合的方法> head ，且带有 permutations-of-rest .
Analysis: string can be split into a head element (character) and the rest of elements, if not empty. Ergo, if we knew how to find permutations of rest, we could find permutations of whole if we'd found a way to combine head with permutations-of-rest.
基本情况 :包含一个空字符串的所有排列的列表是一个空字符串的列表.
Base case: the list containing all permutations of an empty string is a list of one empty string.
组合 :对于静止排列(列表)中的每个排列，插入 head 放在置换元素之间以及两端的每个位置，除非置换为空.在这种情况下，只有一个元素 head 的字符串是唯一的排列结果.
Combination: for each permutation in permutations-of-rest (which is a list), insert head into each position between permutation's elements and also on both its ends, unless permutation was empty. In which case the string with one element, head, is the sole resulting permutation.
归纳步骤 :假设我们已经知道如何置换其余部分.
Induction step: assume we already know how to permute the rest.
完成.
这类事情被称为结构递归"(另请参见此答案)或折叠"或变形":我们将输入拆开，然后将在这些部分上递归应用转换的结果合并，以得到合并的结果.
This kind of thing is known as "structural recursion" (cf. also this answer) or "fold" or "catamorphism": we tear apart an input, and combine the results of recursively applying our transformation on these parts, to get the combined result.
string_permutations [] = [[]]
string_permutations (x:xs) =
for each p in string_permutations(xs):
for each q in insert_everywhere(x,p):
yield q
insert_everywhere(x,abc)必须导致[ [xabc], [axbc], [abxc], [abcx]]，insert_everywhere(x,[])必须导致[ [x] ].
insert_everywhere(x,abc) must result in [ [xabc], [axbc], [abxc], [abcx]] and insert_everywhere(x,[]) must result in [ [x] ].
yield的意思是放入结果整体集合".
yield means "put into the resulting overall collection".
在具有列表理解能力的语言中，以上内容可以写为
In a language with list comprehensions, the above could be written as
string_permutations [] = [[]]
string_permutations (x:xs) = [q | p <- string_permutations(xs)
, q <- insert_everywhere(x,p)]
原理很简单:将其分解为多个部分，递归地处理这些部分，合并结果.当然，诀窍是在每个步骤中保持"true" :不违反某些定律，不破坏某些不变性. IOW较小的问题必须与较大的问题相似" :必须应用相同的法律，使用相同的理论"(即我们可以正确说些什么").
The principle is simple: deconstruct it into parts, do the parts recursively, combine the results. The trick of course is to keep it "true" at each step: to not violate some law about it, to not break some invariant about it. IOW the smaller problems must be "similar" to the bigger one: same laws must apply, same "theories" (i.e. "what we can rightfully say about it").
通常，我们应该以最直接，最简单的方式进行解构.在我们的示例中，我们可以尝试将字符串分成两半-但是组合步骤将很简单.
Usually, we should do the deconstruction in the most direct and simplest way possible. In our example we could have tried splitting the string into two halves - but then the combination step would be non-trivial.
结构递归特别容易:我们首先得到一个结构，该结构通常定义为从其组成部分开始构建. :)您只需要学会放开命令性的挂断，就像对自己说:当我还没有完成事情本身的时候，我该如何处理这些子部分呢?".
Structural recursion is particularly easy: we're given a structure to begin with, which is usually defined as being built from its constituent parts, to begin with. :) You just need to learn to let go of the imperative hang-ups, like saying to yourself "How can I deal with the sub-parts, while I'm not finished with the thing itself, yet?".
头脑中的窍门是想象自己的副本在每个子部分中都遵循完全相同的一组规则，配方和法律来做相同的工作.实际上，这就是在计算机中进行递归调用的方式:对同一过程进行单独的调用(即副本)，但是是在新的新环境框架中(在堆栈"上)进行的.然后，当每个副本完成时，它将结果返回给其调用者，调用者将这些结果组合成其结果.
The mental trick is to imagine copies of yourself doing the same job for each of the sub-parts, following exactly the same set of rules, recipes and laws. And this is actually how a recursive call is done in the computer: a separate invocation - a copy - of the same procedure is made, but in a fresh new environment frame (on "stack"). Then, when each copy is finished, it gives its results back to its invoker, who combines these results to form its results.
(Ah, and reading SICP helps! :) )
这篇关于递归思维的算法是什么? (在特定示例中)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
