计算机科学基础/抽象和递归
只要程序很小，编程就很容易。不可避免地，随着我们创建的程序来解决日益复杂的问题，我们的程序会变得越来越大。我们用来使算法和程序保持简单的技巧之一是抽象，这是一个在艺术、数学和工程等许多领域广泛使用的概念。在本章中，我们将研究如何将这种技术应用于算法设计和编程。
抽象去除细节，帮助我们集中注意力。例如，汽车为驾驶员提供了一组简单的控制作为界面。只要我们知道如何使用界面，我们就可以驾驶汽车，而无需了解它的内部工作原理。汽车的内部工作原理对于驾驶员来说是不必要的细节，除非他们是赛车手，他们需要这种知识才能最有效地驾驶汽车。这种界面自第一辆汽车问世以来就没有太大的变化。抽象还通过从具体例子中提取共同特征来概括概念。这种汽车界面从各种汽车中提取了共同的汽车特征（驾驶员需要了解的驾驶汽车的信息）。一旦你学会了驾驶一辆汽车，你也就学会了驾驶所有同类型的汽车。这是一个强大的想法。这种抽象还使汽车制造商能够自由地改变汽车的内部设计，而不会影响用户。
我们已经了解到，算法设计是使用计算解决问题和编程的第一步。最难的部分不是编程/编码，而是跟踪大型程序中的细节。为了使我们的程序保持“小”，主要有两种方法：分块和分层，这是抽象的两种隐喻。分块将功能分解成更小的单元，并让单元通过定义良好的界面相互交互。例如，在 Snap! 中，你可以将算法实现为一个块，然后只要你能根据界面调用块，并使用正确的参数序列，你就可以在脚本中的任何地方使用它。分层将功能单元（块）分离成不同的层，以分离关注点并简化交互模式，使复杂性更容易管理。下图说明了分层的想法。
通过将功能单元（块）组织成层，我们可以简化交互并允许对层进行并发开发。
在图中，每一层都依赖于它下面的层才能发挥作用，并为它上面的层提供服务。例如，第一层中的一个单元只允许调用它下面的第二层中的单元。所有交互都限制在彼此相邻的层对之间，在一个层堆栈中。我们可以用新的实现完全替换一个层，而不会影响堆栈的其余部分，这实现了模块化。相反，如果允许任何任意交互，我们最终可能会得到紧密耦合的系统，如下图所示。
没有任何限制，任何单元（块）都可以调用任何其他单元。
使用抽象来实现简化和泛化确实是一个强大的组织理念。回想一下第一章中的思维实验，我们构建了一台可以解决方程组的机器。这台机器是通过抽象构建的——我们使用更小的（更基本的）构建块来构建更大的构建块，并将每个块作为一个单元来处理，而忽略内部细节。
Snap! 环境允许我们以类似的方式构建程序。当定义一个块时，它就成为一个新的构建块（用户定义的）。该块可以任意复杂，但要使用它，我们只需要了解它的界面——它的名称和它的参数列表。不必要的细节对用户隐藏，极大地简化了编程所涉及的思考过程。
让我们来看一个具体的例子。为了创建一个精灵来绘制不同的等边形状，我们可以为绘制每种形状（如三角形、正方形、五边形等）创建一个块。Snap! 中的块是一个抽象，它隐藏了细节，代表了某种行为/意图。以下块绘制了一个特定大小的正方形。
这个 Snap! 块绘制了一个特定大小的正方形。
为了绘制三角形，我们可以使用类似的逻辑结构。
这个 Snap! 块绘制了一个等边三角形。
绘制三角形块重复三次，每次绘制一个边，并旋转 120 度。你知道为什么精灵必须旋转 120 度才能在两条边之间形成 60 度角吗？我希望你已经注意到，相同的逻辑结构可以用来创建块来绘制任何等边形状。与其为每个形状创建一个块，我们可以将任务泛化成一个可以绘制任何形状的块。此块需要一个额外的信息——边的数量。
这个 Snap! 块可以绘制任何等边形状。
有了边的数量，我们就可以确定形状的内角，这就是我们绘制形状所需的一切。如果你不确定如何使用边的数量来计算内角，请查看这个资源。这个块可以作为绘制等边形状（多边形）任务的抽象。你可能已经注意到边的长度是硬编码的（作为常量输入，而不是参数）。如果我们想绘制不同大小的形状怎么办？我们可以通过添加另一个参数来进一步泛化块的功能，并使用它来控制边的长度。
这个 Snap! 块可以绘制任何大小的等边多边形。
通过这个例子，我们已经演示了如何定义块以抽象掉任务的细节，并泛化解决方案以解决更多问题。
递归是一种自相似的模式——整体由结构上类似于整体的较小部分组成。例如，树由看起来像小树的树枝组成。类似地，计算机上文件系统的目录树和家谱的家谱树也表现出类似的模式。下图显示了一棵递归树。
使用 Logo 编程语言创建的树，大量依赖递归。
自相似性使我们能够以更简洁、更优雅的方式定义表现出这种模式的概念。树可以是只有一根树干没有分支，也可以是一根树干上有许多分支，而每个分支都是一棵树。这个定义涵盖了所有可能的树结构。你如何描述下图？
-
一种称为 Droste 效应的递归视觉形式。这幅图中的女人手里拿着一件物体，物体中包含着她拿着一件相同物体的较小图像，而物体中又包含着她拿着一件相同物体的更小图像，依此类推。
如果你要通过反复深入到更细的细节来实现，它永远不会结束。你能递归地定义这幅图吗？另一个例子是数学中阶乘函数的定义： 并且对于所有 这个递归定义不仅定义了阶乘，而且还描述了一种计算阶乘的方法。例如，5! 可以从 4! 计算出来，4! 等于 4 乘以 3!，3! 等于 3 乘以 2!，2! 等于 2 乘以 1!，1! 根据定义等于 1。
如果我们解决的问题是自相似的——解决整个问题就是解决与整体相似的部分——那么我们为整体定义的解决方案就可以用于解决子问题（递归）。递归解决方案的妙处在于问题的定义就是解决方案，如阶乘示例所示。为了设计递归解决方案，我们进行“美好愿望式”思考——当我们描述对整个问题的解决方案时，我们希望它已完全定义，可以用于解决较小的子问题。在计算机编程中，这被称为递归式思考/编程。为了进行递归编程，我们将问题的解决方案描述为一个函数/过程/块，在这个函数中，我们将较大的问题分解成较小的问题，并使用我们正在定义的函数来解决较小的问题。如果问题是有限的，最终较小的问题会变得非常简单，可以直接解决。在这种情况下，递归就会停止。我们称这些情况为基本情况。当我们的程序到达所有基本情况时，我们就已经解决了整个问题，因为所有子问题都已解决，包括我们开始时的问题。在任何递归函数中，必须存在两个基本部分：基本情况和递归情况。递归情况部分将较大的问题分解成较小的部分。基本情况通过解决可以直接解决的问题来停止递归。如果这两个部分都存在并且结构合理，该算法（函数）就可以通过要求自身的克隆来解决部分问题来解决任何大小的问题。递归式问题解决是一个强大的理念，因为它简化了我们的思考方式：如果你能递归地定义一个问题，你就可以递归地解决它。递归解决方案更加优雅，也更容易验证，但它只适用于可以递归定义的问题。
在我们研究一些具体的例子之前，我们将介绍函数的概念，它使递归解决方案更容易管理。Snap! 中的一个块如果具有以下属性，则被视为函数（类似于数学函数）
- 一个函数接受任意数量的输入（零个或多个）
- 一个函数始终返回/报告一个结果值
- 对于相同的输入，函数始终报告相同的结果值
- 函数的执行不会对环境产生副作用
在这样的限制下，Snap! 中的函数是独立执行任务（在它自己的世界中）并传递结果以供进一步处理的块。根据这个定义，以下列表中的哪些块是函数？
此列表中的一些块是函数。
考虑二分查找算法
Find an item (target) in a sorted list if the list is empty, the target cannot be found consider the item in the middle, if it matches the target you are done otherwise, decide which half to search next
搜索有序列表的一半仅仅是整个问题的较小版本/部分，所以我们可以应用相同的算法，希望该算法已完全定义。这个过程会一直持续，直到列表为空或找到搜索目标。
显然基本情况是
- 如果列表为空，则找不到目标
- 如果目标位于列表中间，则找到目标
递归情况是（假设列表按升序排序）
- 如果列表中间的项目小于搜索目标，则继续搜索列表的后半部分
- 否则，继续搜索列表的前半部分