从设计范式的角度来看，此处必须介绍两个原则，即(1)分治法(divide and conquer);(2)递归。实际上，一些教科书认为前者包括后者[54],但是这掩盖了关于递归性的重要问题。在这里，我想将它们分开理解，并将递归作为讨论的主要焦点。正如该词所暗示的那样，分治法是一种将问题分解为子问题的方法，解决每个子问题并最后结合所有结果以产生最终结果。处理子问题的最明智且最复杂的方式称为递归。如果需要一个正式的定义，递归是“一种算法技术，其中一个函数为了完成一项任务而自行调用任务的某个部分”。[55]事实上，有时我们有意识地在日常生活中处理递归，例如，道格拉斯·霍夫斯塔特(DouglasHofstadter)就此开了一个与德语相关的玩笑。德语倾向于把动词放在句尾。如果严格遵守语法，我们可能会听到一位教授漫谈整个演讲，最后才挤出一连串的动词，而每位听众都无法理解他所说的意思。[56]为了理解递归，我们必须将它与循环区分。让我们考虑一个例子：给定一个数字x并给定一个整数n,计算x的n次幂。循环方法会在函数本身内计算最多n次乘法。递归方法则将其划分为两种情况，并在函数本身内调用函数，直到满足条件，循环函数的运行时间为O(n),递归函数的运行时间为O(lg(n)),性能显著提高。为使这个例子更加直观，我们可以想象，任务是产生n个镜像：(1)我们可以一个接一个地复制它们(图表19)或者(2)我们可以设置两个面对面的镜子，每一面镜子反射另一面到n/2度(图表20)。
237
论数码物的存在
224