1. 递归简介¶
1.1. 引言¶
如果一个 算法 （或计算机程序中的一个函数）调用自身来完成其部分工作，就称它是 递归的 。 递归使我们可以用简洁、易于理解且算法上高效的程序来求解复杂问题。 递归是这样一种求解过程：把一个大问题化归为一个或多个与原问题结构相同、且稍易于求解的子问题。 一旦完成了最初的划分，子问题又会被划分为复杂度更低的新问题。 最终，子问题会变得足够简单，无需进一步划分即可求解。 最后，把已求解的各个部分重新组合起来，便得到完整的解。
递归方法要取得成功，其"自我调用"所处理的问题就必须比最初尝试解决的问题更小。 一般而言，递归算法必须包含两部分：
基本情况 ，处理无需借助递归调用便能求解的简单输入；
递归部分，其中包含对该算法的一次或多次递归调用。在每一次递归调用中，参数在某些意义上都必须比最初调用的参数"更接近"基本情况。
递归在日常的现实世界问题求解中没有对应物。 这个概念可能难以掌握，因为它要求你用全新的方式思考问题。 初学递归时，人们往往会花很多心思去琢磨递归过程本身。 我们会在这些模块中花一些时间讲解递归工作的细节。 但在编写递归函数时，最好不要再去细想递归调用之后递归是如何运作的。 你应当抱有这样的心态：子问题自会解决好自己，当你递归地调用这个函数时，它自会返回正确的答案。 你只需关心基本情况，以及如何重新组合子问题。
不熟悉递归的新手往往难以接受这样一点：递归主要是一种用来简化算法设计与描述的工具。 递归算法未必总能给出求解该问题最高效的计算机程序，因为递归涉及函数调用，而函数调用通常比 while 循环之类的其他做法代价更高。 不过，递归方法通常能给出一个相当高效的算法。 如有必要，之后可以对这个清晰的递归解法加以改造，得到更快的实现。
设想在电影院里有人问你坐在第几排。 你不想自己去数，于是去问你前面的人坐在第几排，你知道他会告诉你一个比你所在排号小 1 的数。 前面的人又可以再去问他前面的人。 这样一直问下去，直到问话传到第一排，那里的人很容易回答："我坐第 1 排！" 从这里开始，正确的信息（每往回传一排就加 1）最终会传回到发问的人那里。
设想你接到一项大任务。 你可以先做其中一小部分，然后把剩下的 委派 给某个帮手，就像这个例子一样。
让我们深入看看：当你把工作委派出去之后，你的朋友会做些什么。 （注意，我们现在把这个过程展示一遍，等到学习一些递归函数时还会再展示一遍。 但当你编写自己的递归函数时，不必操心所有这些细节。）
要想理解递归，你需要能够做到两件事。 第一，你必须理解如何读懂一个递归函数。 第二，你必须理解如何写出一个递归函数。 这两种能力都需要大量的练习。 所以后面我们会给你安排大量练习。
