什么是递归思维算法？(就具体例子而言)

Question

我只是无法绕过递归.我理解所有的概念(将解决方案分解为更小的案例),并且在我一遍又一遍地阅读之后我能理解解决方案.但我永远无法弄清楚如何使用递归来解决问题.有没有系统的方法来提出递归解决方案？

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

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

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

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

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

• 基本情况是字符串长度= 0时
• 如果它不是基本情况,那么对于字符串的每个第一个字母,将第一个字母插入到字符串的每个排列的每个位置,而不是第一个字母
• 例如:字符串是"abc",第一个字母是a,所以在"bc"的排列的每个位置插入一个.[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

思考过程：

给定：一个字符串。

目标：构建一个包含其所有排列的列表。

涉及的类型：字符串的排列是字符串的列表（集合），其中每个字符串都是输入字符串的某种排列。字符串是字符的列表（序列）。

分析：字符串可以拆分为头元素（字符）和其余元素（如果不为空）。因此，如果我们知道如何找到剩余排列，如果我们找到了一种将head与permutations-of-rest结合起来的方法，我们就可以找到Whole 的排列。

基本情况：包含空字符串的所有排列的列表是一个空字符串的列表。

组合：对于permutations-of-rest（这是一个列表）中的每个排列，将head插入到排列元素之间的每个位置及其两端，除非排列为空。在这种情况下，具有一个元素head的字符串是唯一的结果排列。

归纳步骤：假设我们已经知道如何排列其余部分。

完毕。

这种事情被称为“结构递归”（也参见这个答案）或“折叠”或“变形”：我们分解输入，并将递归地应用我们的变换的结果组合在这些部分上，以获得组合的结果结果。

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] ]。

yield意思是“放入最终的总体集合中”。

在具有列表推导式的语言中，上面的内容可以写成

string_permutations []     = [ [] ]
string_permutations (x:xs) = [ q | p <- string_permutations(xs)
                                 , q <- insert_everywhere(x,p) ]

原理很简单：将其解构为多个部分，递归地执行各个部分，然后组合结果。当然，诀窍是在每一步都保持它的“真实性”：不违反有关它的某些法律，不破坏有关它的某些不变量。IOW，较小的问题必须与较大的问题“相似”：必须适用相同的法律，必须适用相同的“理论”（即“我们可以正确地谈论它”）。

通常我们应该以最直接、最简单的方式进行解构。在我们的示例中，我们可以尝试将字符串分成两半——但是组合步骤将非常重要。

结构递归特别容易：我们首先得到一个结构，该结构通常被定义为从其组成部分构建，首先是。:) 你只需要学会放弃那些势在必行的难题，比如对自己说“我怎么可能处理子部分，而我还没有完成事情本身呢？……”。

心理技巧是想象你自己的复制品对与整个问题相似的每个子部分做同样的工作，遵循完全相同的规则、配方和法律。这实际上就是计算机中递归调用的完成方式：对同一过程进行单独的调用（副本），但在一个全新的环境框架中（在“堆栈”上）。然后，当每个副本完成时，它将其结果返回给其调用者，调用者将这些结果组合起来形成其结果。

^{（啊，阅读 SICP有帮助！:)）}

递归是一种可以帮助我们使编程变得更容易的工具。