问递归思维的算法是什么？(关于具体例子)

EN

思维递归

我认为，为了理解一个复杂的概念，你应该从一个笑话(但正确的)解释开始。

因此，以递归沙拉的定义为例：

Recursive Salad is made of apples, cucumbers and Recursive Salad.

就分析而言，它类似于数学归纳法。

• 你必须定义基础--当工作已经完成，我们必须结束的时候，会发生什么。编写这部分代码。
• 想象一下，流程应该如何从几乎完成的任务逐步过渡到完成的任务，我们如何才能完成最后一步。请自己为the last step编写代码。
• 如果还不能抽象到最后一步-N，请为最后一步创建代码。比较，抽象化。
• 做最后一步-最后一步
• 分析当你开始的时候要做什么。

如何解决一项任务

“把解决方案分解成更小的情况”远远不够。主要原则是：每一个数学任务比2x2更复杂，应该从的末端解决。不仅是递归的。如果你遵守这个规则，数学就会成为你的玩具。如果你不愿意，你在解决任何非偶然的任务时总会遇到严重的问题。

设置任务的方式是不好的。你必须解决任务，而不是用任何具体的方法来解决任务。从目标开始，而不是从给定的工具或数据开始。然后一步一步地移动到数据上，有时使用一些方便的方法。递归解决方案应该自然而然地就会出现在您的面前。或者它不应该，你会用另一种方式做。

阅读G.Polya的“如何解决它”一书。如果你的数学/ it老师没有提出建议，他应该被解雇。问题是99%的人应该被解雇..。-(。不要认为，互联网上的引用就足够了。读这本书。是the king's way into maths。

如何考虑递归示例

(代码不是真正的Java) (代码并不打算有效)

我们需要:一个包含所有不同字符的字符串的排列列表。

它可以写成列表

因此，当函数准备就绪时，将接受要置换的字符串并返回该列表。

List<String> allPermutations(String source){}

要返回该列表，函数必须具有局部变量的列表。

List<String> allPermutations(String source){
  List<String> permutResult=new List<String>();
  return permutResult;
}

让我们想象一下，我们已经找到了几乎整个字符串的排列，但是找到了其中的最后一个字符。

List<String> allPermutations(String source){
  List<String> permutResult=new List<String>();
  ...we have found permutations to all chars but the last
  We have to take that last char and put it into every possible place in every already found permutation.
  return permutResult;
}

但是，这已经找到了排列，我们可以写作为我们的函数，为一个更短的字符串！

List<String> allPermutations(String source){
  List<String> permutResult=new List<String>();
  permutFound=allPermutations(substr(source,source.length-1));
  for (String permutation: permutFound){
    for (int i=0;i<=permutation.length;i++){
      String newPermutation=permutation.insert(source[last],i);
      permutResult.add(newPermutation);
    }
  }
  return permutResult;
}

很高兴，我们不需要计算和使用源字符串的当前长度--我们经常使用最后一个字符.但是开始呢？我们不能在空源中使用我们的函数。但是我们可以这样改变它，这样我们才能这样使用它！首先，我们需要一个带空字符串的置换。我们也把它还回去吧。

List<String> allPermutations(String source){
  List<String> permutResult=new List<String>();
  if (source.length==0){
    permutResult.add("");
  }     
  permutFound=allPermutations(substr(source,source.length-1));
  for (String permutation: permutFound){
    for (int i=0;i<=permutation.length;i++){
      String newPermutation=permutation.insert(source[last],i);
      permutResult.add(newPermutation);
    }
  }
  return permutResult;
}

因此，我们最终使程序开始工作，也。就这样。

你可以试着考虑如何解决这个问题，解决一个更简单的问题。如果你已经解决了尺寸i的问题，你会如何解决?如果步骤i和前面的步骤都已经解决了，你将如何在第一步解决这个问题。

递归是通过归纳[1]来思考的。

在排列的情况下，基本大小写是ok的(它也可以是一个空字符串或带有1个元素的字符串，该字符串的置换是相同的字符串)。

但是您的归纳步骤失败了，试想如果您的字符串的长度为i，并且您已经有了一组长度字符串的排列(i-1)，那么如何通过增加第一个字符来创建字符串的所有排列呢？

现在，在一些小的情况下，比如两个元素：{ "ab“，"ba"}如果给您第三个元素"c"，那么如何使用上面的元素和”ab“的解决方案创建字符串"abc”的排列呢？

答案是：{"cab“、"acb”、"abc“、"cba”、"bca“、"bac"}

注意，在"c“的位置，它会被插入到前一个解决方案中的每个字符串的每个位置。即(伪码)：

res = {}
for s in {"ab", "ba"}:
  for i = 0 to len(s):
    res.add(s.insert("c", i))

现在，将{"ab“、"ba"}替换为使用i-1字符串的递归调用，这样就有了递归函数。

如果这还不够清楚的话，可以随便问一下。

如果你熟悉递归，我认为递归是一种更直观的解决方法。简单的规则是，将您的函数想象为同一个函数与较小的输入的组合。在某些情况下，递归比其他情况更明显。例如，排列就是这样一种情况。想象一下permut(S) = List{a+permut(S-{a})} for all a in S，其中S由独特的字符组成。思想是在字符串中选择一个字符，并将其与其余字符的所有排列连接起来，这将给出以该字符开头的所有字符串的唯一排列。

示例伪代码：-

Permutation(S,List) {

    if(S.length>0) {

        for all a in S {

            Permutation(S.remove(a),List.add(a));
        }

    }

    else  print List;

 }

根据我的理解，上面的代码对于置换来说是最简单的，因为它直接翻译了递归关系，在这种关系中，我们从字符串中选择一个字符，然后将它连接到所有其他较小字符串的组合中。

备注：-使用数组和交换可以更有效地完成这一任务，但对于理解来说则要复杂得多。