algorithm - 递归思维的算法是什么？ (在具体例子上)

Question

我只是无法理解递归。我理解所有的概念(将解决方案分解成更小的案例)，并且在一遍又一遍地阅读它们之后我可以理解解决方案。但是我永远想不通如何使用递归来解决问题。有什么系统的方法可以提出递归解决方案吗？

有人可以向我解释一下他们在尝试解决以下递归问题时的思考过程吗:“使用递归返回字符串的所有排列”。

这是我解决这个问题的思考过程的一个例子。

• 检查字符串长度是否等于 2。如果是，交换值(基本情况)
• 否则:对于每个第一个值返回第一个值+递归(没有第一个值的字符串)

有人可以给我一些提示来改变我的思维过程或以更好的方式思考递归，这样我就可以解决递归问题而不仅仅是查找答案。

编辑:这是我为这个问题编写另一个解决方案的思考过程。

• 基本情况是字符串长度 = 0
• 如果不是基本情况，则对于字符串的每个第一个字母，将第一个字母插入到字符串的每个排列的每个位置，而不是第一个字母
• 例如:字符串是“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);
        }
     }
   }
}

Answer 1

递归思考

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

因此，采用递归沙拉的定义:

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

至于分析，它类似于数学归纳法。

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

如何解决任务

“将解决方案分解成更小的案例”是远远不够的。主要规则是:每个数学任务比 2x2 更复杂，应该从头开始解决。不仅是递归的。如果您遵循该规则，数学将成为您的玩具。如果您不这样做，那么您在以非偶然方式解决任何任务时总会遇到严重问题。

你的任务设置方式不好。你必须解决任务，而不是通过任何具体的事情来解决任务。从目标开始，而不是从给定的工具或数据开始。并一步一步地移动到数据，有时使用一些方便的方法。递归解决方案应该自然而然地自动出现。或者它不应该，你会用其他方式来做。

阅读 G.Polya 的《How to Solve It》一书。如果你的数学/IT 老师没有建议，他应该被解雇。问题是，他们中的 99% 应该被解雇……:-(。不要认为，互联网上的引用就足够了。读这本书。这是数学之王.

---

如何思考递归 - 例子

(代码不是真正的 Java)(代码不是为了有效)

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

可以写成List

因此，该函数准备就绪时，将获取要排列的字符串并返回该列表

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;
}

所以，最后我们让程序也能在启动时运行。就这样。