掌握递归编程

Question

掌握递归编程

algorithmrecursiondata-structuresrecursive-datastructures

53

我在递归方面遇到了问题，无法思考或解决问题。我非常赞赏这一概念，能够理解创建基本情况、退出情况和递归调用等内容。我可以解决简单的问题，比如编写阶乘或整数数组求和。这就是我的思维停止的地方。当问题变得复杂时，我无法真正应用这些概念或想出解决方案。例如，汉诺塔问题，虽然我可以理解问题和解决方案，但我自己无法想出解决方案。其他算法，如快速排序/二叉树遍历也都是如此。所以我的问题是：

掌握它的最佳方法是什么？
有人能推荐一系列问题或题目，供我练习吗？
学习函数式语言会帮助我理解吗？

请给予建议。

- Hunter

4

递归之所以难理解，是因为我们在年幼时没有学会递归思维方式。我发现在解决递归问题时，先考虑基本情况会很有帮助。一旦成功确定了基本情况，接下来的构建过程就相对容易了。这种方法对我很有效。 - Paulo Bu

我在学习递归时发现有一个思路很有帮助： “递归是将问题简单化的方法，通常表现为你的解决方案 = 简单步骤 + 稍微更容易的解决方案” 例如，在汉诺塔问题中，我使用以下推理来解决它：通过以下方式解决该问题： a）将最大的一块（单独）从点1移动到点3（简单步骤） b）将n-1个塔从点2移动到点3（稍微更容易的解决方案）稍微更容易的解决方案可以通过重复步骤a）和b）找到，只需针对目标点2等进行即可... - Davide

2

递归是关于抽象的。您尝试以与原始问题相同的格式表达问题的解决方案，但使用不同的参数。例如，10！= 1 * 10！= 10 * 9！，因此问题和解决方案都采用a * b！的形式。大多数人发现抽象很难。但实际上，这就是尝试在不同情况下找到相似之处。您甚至可以在日常生活中练习这一点（尝试看到两个不同概念的相似之处）。 - Vincent van der Weele

1

递归（和归纳证明）通常不是一下子就能理解的东西，尽管它通常并不是非常复杂。一个好的方法就是确实学习下面回答中提到的问题，并尝试递归地构造问题和结构，即使这看起来完全是人工的。但我想补充一下极小化算法，它可以用于玩几种棋类游戏。它也可以被看作是导航搜索树。 - Codor

练习：列举出字符串 'abcdefgh' 的所有排列组合，或者从这个集合中找到所有由5个字母组成的组合。提示：假设您有一个函数可以枚举 'abcdefg' 的所有排列组合；假设您有一个函数可以枚举 'abcdefgh' 中4个字母的所有组合；或者假设您有一个函数可以在 'abcdefg' 中枚举所有由5个字母组成的组合。 - user1196549

一篇关于递归的精彩答案，来自用户@Barney：http://stackoverflow.com/a/22242301/2736496。虽然它是关于在2D数组中解决0/1迷宫问题，但同时也涉及了递归的一般性问题。 - aliteralmind

6个回答

12

我的建议是：相信递归函数“能够完成任务”，即满足其规范。有了这个认识，您可以构建一个函数来解决更大的问题，同时仍然满足规范。

如何解决汉诺塔问题？假设有一个名为Hanoi（N）的函数，能够在不违反规则的情况下移动N个盘子的堆。使用此函数，您可以轻松实现Hanoi'（N+1）：执行Hanoi（N），移动下一个盘子，再次执行Hanoi（N）。

如果Hanoi（N）有效，则Hanoi'（N+1）也有效，而不会违反规则。为了完成论证，您必须确保递归调用终止。在这种情况下，如果您可以非递归地解决Hanoi（1）（这是微不足道的），那么您就完成了。

使用这种方法，您不必担心事情实际上会发生什么，您保证它有效。（前提是您转移到问题的较小和较小的实例。）

另一个例子：二叉树的递归遍历。假设函数Visit(root)完成了任务。那么，if left -> Visit(left); if right -> Visit(right); print root就可以完成任务！因为第一次调用将打印左子树（不必担心如何），第二次调用将打印右子树（不必担心如何），并且根也将被打印。

在后一种情况下，终止是由于您处理越来越小的子树，直到叶子节点。

另一个例子：快速排序。假设您有一个原地对数组进行排序的函数，称为Quicksort。您将按以下方式使用它：通过将它们与精心选择的“枢轴”值（实际上，数组中的任何值都可以）进行比较，将小元素移动到大元素之前，就地排序。然后通过Quicksort函数对小元素进行排序，以相同的方式对大元素进行排序，然后您就完成了！无需考虑将发生的确切分区序列。如果避免空子数组，则可以确保终止。

最后一个例子是帕斯卡三角形。你知道一个元素等于它上面两个元素之和，两侧为1。所以可以闭着眼睛写出这个代码：C(K, N)= 1 if K=0 or K=N, else C(K, N) = C(K-1, N-1) + C(K, N-1)。就是这样！

- user1196549

3

递归很难，因为它是一种不同的思考方式，当我们年幼时从未接触过。

根据你的说法，你已经掌握了概念，只需要多练习。使用函数式语言一定会有帮助；你会被迫递归地思考问题，在你意识之前，递归就会变得非常自然。

有很多与递归相关的练习可以做，记住任何使用循环完成的事情也可以用递归来完成。

请参见此答案，其中有关于引用和练习问题的很好的细节说明。

- Moha the almighty camel

3

递归是实现分治范式的方便方式：当您需要解决一个问题时，一种强大的方法是将其分成性质相同但规模较小的问题。通过重复此过程，您最终将处理规模足够小以便通过另一种方法轻松解决的问题。

您需要问自己的问题是“我能通过解决部分问题来解决这个问题吗？”当答案是肯定的时候，您应该应用这个众所周知的方案：

1.递归地将问题分解为子问题，直到大小很小，

2.通过直接方法解决子问题，

3.反向合并解决方案。

请注意，拆分可以在两个或多个部分中进行，并且可以平衡或不平衡。

例如：我可以通过执行部分排序来对数字数组进行排序吗？

答案1：是的，如果我将最后一个元素剔除并对其余元素排序，则可以通过将最后一个元素插入到正确的位置来对整个数组进行排序。这就是插入排序。

答案2：是的，如果我找到最大的元素并将其移动到末尾，则可以通过对其余元素进行排序来对整个数组进行排序。这就是选择排序。

答案3：是的，如果我对数组的两半进行排序，则可以通过使用辅助数组进行移动来合并两个序列，从而对整个数组进行排序。这就是归并排序。

答案4：是的，如果我使用枢轴分区数组，则可以通过对两部分排序来对整个数组进行排序。这就是快速排序。

在所有这些情况下，您通过解决性质相同的子问题并添加一些粘合剂来解决问题。

- user1196549

3

学习一门函数式语言会有助于您思考递归。我推荐使用 Haskell 或 Lisp（或 Clojure）。好消息是，在学习递归之前您不需要接触这些语言的“难点”。为了学习递归，您不必学习足够多的这些语言来进行“真正”的编程。

Haskell 的模式匹配语法使得基本情况易于理解。在 Haskell 中，阶乘看起来像这样：

factorial 0 = 1
factorial n = n * factorial (n - 1)

这与过程语言的以下代码完全等价：

int factorial(n) {
    if(n==0) {
         return 1;
    } else {
         return n * factorial(n-1)
    }
}

...但使用更少的语法来阐明概念。

为了完整起见，以下是同样的算法在Lisp中的实现：

(defun factorial (n)
   (if (== n 0)
       1
       (* n (factorial (- n 1)))))

你应该能够看出这是等价的，虽然一开始所有的括号往往会遮盖人们对正在发生的事情的视野。不过，Lisp书籍将涵盖许多递归技术。

此外，任何一本关于函数式语言的书都会给你很多递归示例。您将从处理列表的算法开始：

 addone [] = []
 addone (head:tail) = head + 1 : addone tail

这里讲的是一种常见的模式，每个函数只有一个递归调用。（实际上这个模式非常常见，几乎所有语言都把它封装成叫做 map 的库函数）

然后你将会学习遍历树形结构的函数，通过为每个节点的每个分支进行一次递归调用。

更一般地说，可以像这样思考问题：

“我能解决这个问题的一小部分，让自己只剩下相同的问题吗？”

或者...

“如果问题的其余部分已经被解决，那么这个问题是否容易解决？”

例如，如果知道factorial(n-1)，就可以简单地解决factorial(n)，这表明递归是一个可行的解决方法。

事实证明，很多问题都可以用这种方式思考：

“对1000个项目的列表进行排序似乎很难，但如果我选择一个随机数，先将所有比该数小的数字排序，再将所有比该数大的数字排序，就完成了”。（最终要排序长度为1的列表）

...

“计算到一个节点的最短路径很难，但如果我只知道从相邻节点到达该节点的距离，它将变得容易。”

...

“访问此目录树中的每个文件很难，但我可以查看基本目录中的文件，并以相同的方式处理子目录。”

同样地，河内塔问题也是如此。如果按照以下方式表述，解决方案将会很容易：

 To move a stack from a to c:
  If the stack is of size 1
      just move it.
  otherwise
      Move the stack minus its largest ring, to b (n-1 problem)
      Move the largest ring to c (easy)
      Move the stack on b to c (n-1 problem)

我们通过概述两个看似困难的步骤，使问题看起来很容易。但是这些步骤只是相同的问题，只不过“更小一些”。

您可能会发现手动逐步执行递归算法并使用纸片表示调用堆栈很有用，如此答案所述：Understanding stack unwinding in recursion (tree traversal)

在您更加熟悉递归之后，请回过头来思考它是否是特定情况下的正确解决方案。虽然 factorial() 是演示递归概念的好方法，但在大多数语言中，迭代解决方案更有效。了解尾递归优化，哪些语言具有这种功能以及原因。

- slim

关于Clojure的一点小笔记——由于Java的工作方式（缺乏尾递归优化），Clojure实际上避免在许多正常的Lisp使用递归的情况下使用它。因此，学习递归可能并不是学习Clojure的最佳资源。 - slim

Clojure有recur，它不会导致堆栈溢出。Common Lisp没有尾递归优化，因此依赖于loop，而Scheme即使对于相互（尾）递归调用也保证进行尾递归优化。 - Sylwester

2

对于复杂问题，建议从小规模问题开始，了解其中的模式。例如，在汉诺塔游戏中，从一个问题大小开始，然后是两个，接着是三个，以此类推。在某些时候，您可能会开始看到一些模式，并且意识到您所做的一些事情与较小规模问题时所做的一样，或者非常相似，因此您可以使用以前相同的技巧，但要有所改变。

我刚刚自己解决了汉诺塔问题并研究了自己的思维过程。我从大小为一的问题开始：

我们的A柱上有一个盘子。 ***将其移至C柱。完成！

现在是两个盘子。

我们在A柱上有两个盘子。我需要用B柱来挪动第一个盘子。 ***将其从A柱移至B柱现在我可以解决其他的部分了 ***将其从A柱移至C柱 ***将其从B柱移至C柱完成！

现在是三个盘子。

事情开始变得更加有趣。解决方案不是那么明显。然而，我已经找到了如何将两个盘子从一个柱子移动到另一个柱子，因此如果我能将两个盘子从A柱移动到B柱，然后将一个盘子从A柱移动到C柱，然后再将两个盘子从B柱移动到C柱，那么我就完成了！我的逻辑对于两个盘子的情况可以奏效，只是柱子不同而已。如果我们将此逻辑放入函数中，并为柱子设置参数，则可以重复使用该逻辑。

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   print 'Move from peg '+from_peg+' to peg '+other_peg
   # Now I can do the rest
   print 'Move from peg '+from_peg+' to peg '+to_peg
   print 'Move from peg '+other_peg+' to peg '+to_peg

其逻辑如下:

       move2('A','B','C')
       print '从柱子 A 移到柱子 C'
       move2('B','C','A')

我可以通过另外一个函数 move1 来使这段代码更简便:

def move1(from_peg,to_peg):
    print 'Move from '+from_peg+' to '+to_peg

现在我的move2函数可以：

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   move1(from_peg,other_peg,to_peg)
   # Now I can do the rest
   move1(from_peg,to_peg)
   move1(other_peg,to_peg)

好的，那么四怎么办？

看起来我可以应用同样的逻辑。我需要将三个盘子从A柱移动到B柱，然后将一个盘子从A柱移动到C柱，最后将三个盘子从B柱移动到C柱。我已经解决了移动三个盘子的问题，但是使用了错误的柱子，所以我会将其概括为：

def move3(from_peg,to_peg,other_peg):
   move2(from_peg,other_peg,to_peg)
   move1(from_peg,to_peg)
   move2(other_peg,to_peg,from_peg)

很酷！等等，现在move3和move2非常相似，这是有道理的。对于任何大小的问题，我们可以将除了一个盘子以外的所有盘子移动到B柱，然后将一个盘子从A柱移动到C柱，最后将B柱上的所有盘子移动到C柱。因此，我们的移动函数可以将盘子数量作为参数：

def move(n,from_peg,to_peg,other_peg):
    move(n-1,from_peg,other_peg,to_peg)
    move1(from_peg,to_peg)
    move(n-1,other_peg,to_peg,from_peg)

这看起来非常接近，但在n==1的情况下不起作用，因为我们最终会调用move(0,...)。所以我们需要处理一下：

def move(n,from_peg,to_peg,other_peg):
    if n==1:
        move1(from_peg,to_peg)
    else:
        move(n-1,from_peg,other_peg,to_peg)
        move1(from_peg,to_peg)
        move(n-1,other_peg,to_peg,from_peg)

太好了！如果问题的规模为5怎么办？我们只需要调用move(5,'A','C','B')。看起来任何问题的规模都是一样的，因此我们的主函数只需：

def towers(n):
    move(n,'A','C','B')

我们完成了！

- Vaughn Cato

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paulo Bu · Accepted Answer

递归只是一种思维方式，就像迭代一样。当我们还在学校时，我们没有被教授如何递归地思考，这就是真正的问题所在。你需要将这种思维方式纳入你的工具库中，一旦你做到了，它就会永远留在那里。

掌握的最佳方法：

我发现首先找出基本情况非常有用，也许起初它们并不是最简单的，但一旦你开始在这个基本情况上构建递归，你会意识到你可以简化它。确定基本情况的重要性在于，首先，你专注于以最简单的形式解决问题（较简单的情况），这在某种程度上为未来的算法提供了路线图；其次，你确保算法停止。也许不返回期望的结果，但至少停止，这总是令人鼓舞的。

此外，弄清楚一个问题的小实例如何帮助你找到更大实例的解决方案，总是很有帮助。例如，你如何在已经有输入 n-1 的情况下构建输入 n 的解决方案。

尝试用递归解决你能想到的每个问题。是的，汉诺塔不是一个很好的例子，它的递归解决方案是一种非常聪明的解决方案。试试更简单的问题，几乎是最基本的问题。

问题列表

数学操作：指数运算和所有你能想到的数学运算。
字符串处理：回文是一个很好的练习。在网格中查找单词也很有用。
学习树形数据结构：这特别是我认为最好的训练。树是递归数据结构。学习它们的遍历（中序、后序、前序），计算它的高度、直径等。几乎对于树形数据结构上的每个操作都是一个很好的练习。
组合问题：非常重要，组合、排列等等。
路径查找：李氏算法、迷宫算法等等。

但最重要的是，从简单问题开始。几乎每个问题都有一个递归解决方案。数学问题非常适合掌握此技巧。每次看到 for 循环或 while 循环时，请将该算法转换为递归。

编程语言

函数式编程非常依赖于递归。我认为这可能不会对不太了解递归的用户有太大帮助，因为它们本质上是递归的，并且可能很繁琐。

使用一种简单的编程语言，最好是你最熟悉的一种，最好是那种不会让你在内存麻烦和指针方面感到困扰的语言。在我看来，Python 是一个非常好的开始。它非常简单，不会让你感到烦恼，也不会让你感到类型或复杂数据结构的麻烦。只要这种语言帮助您专注于递归，它就会更好。

最后一个建议是，如果您找不到问题的解决方案，请在互联网上搜索或寻求帮助，完全理解它的作用，然后转移到其他问题。不要让它们绕过你，因为你正在尝试将那种思考方式加入你的脑中。

要 掌握递归，首先需要 掌握递归 :)

希望这有所帮助！