视频库 / NO.015
--:--
点击播放，这里会跟随视频显示当前句的中英字幕。
MIT Godel Escher Bach Lecture 2
节目发布 2012-12-02 · jasonofthel33t
本期追问 · 点击跳到视频对应位置
26:21 一条简单规则反复施加，怎么长出无限复杂的图形？49:06 代码里没写递归，递归还会藏在哪一层？20:10 有限的面积为什么能被无限长的边界围住？69:28 句子套句子和巴赫的和声嵌套，是同一回事吗？
归入 Ⅰ·05 整体能大于部分之和吗？ →EDITED TRANSCRIPT · 依据现场录音编译整理，可划线生成便签
编者按：2007 年夏天，MIT 开设了一门以侯世达（Douglas Hofstadter）名著《哥德尔、埃舍尔、巴赫》为读本的研讨课。本次第二讲的原定讲者贾斯汀·柯里缺席，由柯伦·凯莱赫（Curran Kelleher）代课，他带着自己用 Groovy/Java 写的一组程序，从阶乘一路讲到分形蕨、曼德博集合与巴赫的和声迷宫。课堂上有学生反复追问，从「把科赫雪花剪断能拉多长」到「代码里没有递归函数，怎么知道输出是递归的」，把讲者一步步逼到递归定义的边界上。本文依据现场录音编译整理，只删去口语枝节、寒暄与重复，论证、例子与现场问答均予保留。
阶乘：递归的起点
凯莱赫： 我叫柯伦·凯莱赫，今天由我来讲递归和分形。贾斯汀今天不在，所以我替他上这一课。我准备了一批例子，都是递归的计算机程序，有的不画图，有的画图，凡是画图的，画出来的都是分形。所谓分形（fractal），就是在不同尺度上自相似的东西，你可以一直放大下去。我们四点休息十分钟，然后我会给你们看一批分形的例子，再放几段巴赫。
凯莱赫： 先看一个递归的数学函数：阶乘。三的阶乘是 3×2×1，四的阶乘是 4×3×2×1，就是那个感叹号。它的定义本身其实就是递归的：任意一个 n 的阶乘，等于 n 乘以 (n-1) 的阶乘。比如 n 是四，n 减一就是三，四的阶乘就是四乘以三的阶乘。这是一个递归定义。
凯莱赫： 讲义第三页上有我写的一个小程序，就是做阶乘的。给不太熟悉编程的同学解释一下：def 的意思是「定义」，所以我们在定义一个叫 factorial 的函数，它接受一个参数 n。你可以调用这个函数，传给它一个数，在函数内部，这个数就叫 n。函数体是这样的：如果 n 大于 1，就返回 n 乘以 factorial(n-1)；否则，返回 1。
凯莱赫： 让这个函数成为递归函数的，恰恰是它调用了它自己。阶乘被定义成 n 乘以另一个东西的阶乘。所以，递归函数就是调用自身的函数。举个例子，假设 n 是五，我们调用 factorial(5)，函数拿到 n 等于五。五大于一，于是返回五乘以 factorial(4)。四也大于一，于是返回四乘以 factorial(3)，也就是五乘四乘以三的阶乘。它就这样一层层调用自己，一直降到 1 为止。这就是递归。
斐波那契数列
凯莱赫： 另一个跟阶乘很像的简单例子，是斐波那契数（Fibonacci numbers）。数列是这样的：1，1，然后把前两项加起来得到下一项，于是 1，1，2；1 加 2 是 3；2 加 3 是 5；再来是 8，如此往下。这些就是斐波那契数。
凯莱赫： 这同样是一个递归定义。这里的编号只是元素的下标。斐波那契的第二项等于第零项加第一项，第五项等于第三项加第四项。一般地说，fib(n) 等于 fib(n-1) 加 fib(n-2)。所以我们把刚才那段代码里的 factorial 换成 fib 就行了，你会发现两者几乎一模一样：如果 n 大于 1，就返回 fib(n-1) 加 fib(n-2)。这样就得到了斐波那契数列。讲义里两个程序的样例输出都有，跑出来就是这个结果。
递归转移网络
凯莱赫： 今天谁带了《哥德尔、埃舍尔、巴赫》？请翻到第 132 页。那里有两张图，是递归转移网络（recursive transition network）。它们定义了一套语法，有点像英语。它当然不是完整的英语，只是一个简化版，但作者要传达的语法本质，也就是递归语法的意思，已经完整地在里面了。
凯莱赫： 你会看到，「花哨名词」（fancy noun）这个节点里又调用了「花哨名词」自己，箭头绕回到了自身。递归就在这里。我做的事情，是把这张图改写成一个小程序：凡是遇到岔路，也就是有多条转移可选的地方，程序就随机挑一条走。这个程序在我讲义的第五页。可惜投影仪不能用，不然我就直接放给你们看了。
凯莱赫： 我们照着图看。「花哨名词」一开始就调用「普通名词」（ordinate noun）。再看讲义里的程序，大概在中间靠下的位置，写着「fancy noun 的 RTN」，然后是 fancy noun 等于某个函数调用。先说明一下，在这门语言里，给一段东西套上花括号，它基本上就成了一个函数。所以 fancy noun 等于什么呢？基本上是从图里照抄下来的：先调用 ordinate noun，然后从「介词」、「关系代词」、「什么都不接」这几项里随机挑一个。你去看书上那张图，从 ordinate noun 出来的箭头，正好指向关系代词、空、结束和介词这几处。你完全可以把它写成一个计算机程序，我做的就是这件事。
凯莱赫： 你把我的程序多看一会儿就会发现，图里所有的箭头都对应着程序里的函数调用，而它们之所以是递归的，是因为兜兜转转最后会绕回自身。侯世达在这里要说明的是：语言本身就是由递归语法定义的。这正是我们能把句子套在句子里的原因，它是递归的。递归带来嵌套，有时候是无穷的嵌套，而这正是分形的来处。
凯莱赫： 程序后面就是样例输出，你们读一读，挺好玩的。比如「奇怪的母牛里面的小小百吉饼」，作为一个英文句子居然说得通，而它是这个程序生成的。我觉得这件事本身就非常迷人。当然也有完全不知所云的，比如「跑着大小大号角的大小百吉饼」，这句就毫无意义。
递归画树
凯莱赫： 下一个例子在第五页，我们要用递归函数画一棵树。我在黑板上写一段伪代码，不是真正的代码，只是把这个程序在做什么讲清楚。
凯莱赫： 我们有一个「长树」的函数，从一根枝条开始。这里是起点，是入口。程序一启动，就会执行主类里那句 tree()。第一次调用 growTree，参数是 0.5、0、树干高度等等，画出来的就是最下面这一根。这一步启动了整个过程。函数里做的事情，基本上就是：只要深度大于零，就往下做。
凯莱赫： 这个函数会调用自己两次，一次一条分枝。程序第一次调用它，就画出这一根，直接画在屏幕上。你注意看代码里那句 add new JV line X1 X2，那一句才是真正往屏幕上添一条线。我真希望能把程序跑起来给你们看。depth 是它要分叉的次数，这里 depth 是 11，所以会长成一棵很大的树。
凯莱赫： 接下来它生成两条子枝，两次 growTree 调用分别对应这一条和那一条。看讲义里的代码：growTree(X2, Y2, ...)，X2、Y2 就是上一根枝条的末端；rootLength 乘以 sizeFactor，sizeFactor 是缩放系数，这里是 0.58，所以每一级大约缩小到一半；再看角度，一个是 rootAngle 加 angleFactor，一个是 rootAngle 减 angleFactor。angleFactor 是 π/4，正好 45 度。所以每分一次叉，两条枝就按这个角度岔开。
凯莱赫： 假设第一次调用时 depth 是四，进到函数里传给下一层的是 depth 减一，于是里面这一层的 depth 是三，再往下是二、一，一直减到零为止。左右两边都这样做，就这么一直长下去。这就是一个分形。你可以设想，如果不写 depth 等于 10 或者 11，而是写 depth 等于无穷，理论上这个形状就可以无限放大下去，永远放大下去，而且放大之后看上去和大尺度上一模一样。这就是分形的概念。树的部分有问题吗？
科赫曲线
凯莱赫： 接下来是科赫曲线（Koch curve）。它和树很像，只是规则不同。先讲概念上它是什么：你从一条线段开始，有时候是从一个三角形开始（那样能做出整个雪花），把线段三等分，用中间那一段作边长，向外做一个等边三角形，也就是三边等长，然后把中间那条原线段去掉。这就是规则：从一条线变成这个折线形状。然后把同一条规则施加到新生成的每一小段上，再往下，继续对更小的段做同样的事。
凯莱赫： 一条简单的规则被反复施加，而每次施加的对象都是上一次施加规则的结果，这就是递归。你可以一直画下去。我们看代码，在第七页，函数叫 createCurve。它做的事情本质上就是调用自己四次，这四次分别对应折线的这一段、这一段、这一段和这一段。
凯莱赫： 看代码中间那四个 createCurve 调用，参数是 X1、Y1、AX、AY、CX、CY、BY 等等。对照那张红色小图：这个点是 X1、Y1，其他点在图里都标好了。第一个调用的意思是，把规则施加到这一段上；第二个从 A 点开始，也就是这里，把规则施加到那一段；第三个从 C 开始，C 是顶点；第四个施加到最后一段。这又是一个漂亮的递归分形。
凯莱赫： 如果把它推广一下，加进随机性，会发生什么呢？这些点的名字无所谓，关键是，不要让它们落在精确的位置上，而是让每个点上下随机偏移一点点，然后连线，在那里做出三角形，这里也偏一点。每一步都掺一点随机，你画出来的线条就和真实的海岸线一模一样，就是陆地边缘的那种轮廓。如果再把它推广到三维，同样加随机，生成出来的就是三维山脉，虚拟的三维曲面，看上去和真山没有分别。所以有点奇怪：这些递归结构确实存在于自然界。
有限面积，无限周长
学生： 第六页上写着，科赫雪花的面积是有限的，但周长是无限的，这是什么意思？
凯莱赫： 对，我刚才忘了讲，这一点特别有意思。科赫雪花是从一个三角形出发，对三角形的每一条边施加那条规则，三条边上都长出这样的曲线。数学上已经证明，或者说已经推演出来：如果你把这条规则施加无穷多次（在数学里可以这么做，因为它是纯理论的），这个图形内部的面积是有限的，是一个确定的数值。但它的表面积，不对，是周长，周长是无限的。原因在于，你每施加一次规则，周长都会变长。原来这一段有一个长度，施加规则以后，新的折线总长比原来更长。你可以想见，如果无限地做下去，它就会无限长。这真是让人头晕。
学生： 可是每迭代一次，新加的那些段不是越来越小吗？
凯莱赫： 确实越来越小。但如果你在理论上做无穷多次，它依然存在。你看第六页标题「科赫雪花」旁边那条曲线，看到了吗？即使做无穷多次，大致就是那个样子。
学生： 那假如我把这样一片雪花剪开呢？比如我把它剪成两半，再把它拉开，它会一直延伸下去吗？
凯莱赫： 你是说从中间剪断？
学生： 不是剪成两半，就是在某一处剪开。我不是要让各段互相跑到别处去，只是像剪一根围成圈的绳子那样剪一刀。
凯莱赫： 我不太确定我理解了，你要不上来画一下。
学生： 比如说我这里有一个圈，我在这个位置剪一刀。你刚才说它面积是有限的，那我这样剪开再拉直，它就能一直延伸下去，可这说不通啊。
凯莱赫： 我明白了，你说的是它同时又有有限的面积。就是说，假如这条科赫曲线是一根绳子，你把它剪断，绳子就散开了，然后你去拉它，它会一直延伸下去。是的，确实如此。这就是「周长无限」的意思，所以它才这么迷人，简直是疯了。
英国海岸线有多长
凯莱赫： 有人真的试过去量不列颠的海岸线。英国的海岸线有多长？你们听过这个问题吗？如果你从很大的尺度上看，比如整个国家的卫星照片，你可以沿着轮廓画一圈线，然后说：好，就这么长，这就是英国海岸线的长度。但你一放大就会发现，刚才画的那些大线段其实错得离谱，根本对不上真实的边界。于是你按照新的放大倍率把它画得更精细，结果长度变长了。
学生： 可是新加进去的那些不是应该越来越小吗，你只是补上一些小碎块而已。
凯莱赫： 对，只是补上一些小碎块。假设真实的海岸线是这个样子，你从极远处看，会说：好，大概就是这条直线。但你看得更仔细、把它细化以后就会说：不对，不是那条直线，大概是这几条折线。可是这些新折线加起来，总长度比原来更长。你再精细一点，再精细一点，它就越来越长、越来越长。所以从来没有人真正算出英国海岸线有多长。它是一个分形。
学生： 可是在这个现实世界里，真的可能存在无限精细的东西吗？那不是得有无穷小的尺度才行？
凯莱赫： 他问的是，在这个世界上有没有可能真的存在那样的无限。答案是没有，因为地球上的空间是有限的。
学生： 但就算在有限的范围内，你刚才不也说，就算面积或者体积是有限的，周长还是可以无限吗？
凯莱赫： 是的，科赫曲线在数学的语言里，如果你严格按数学去做，它的周长无限而面积有限。但要记住，这是一个理论上的造物，它只活在数学世界里，在宇宙中无法真正存在。不过自然界里有很多东西非常接近它。英国的海岸线并不是真的无限长，但它确实非常像这一类形状。科赫曲线还有别的问题吗？
谢尔宾斯基三角形
凯莱赫： 下一个例子在第八页，谢尔宾斯基三角形（Sierpinski triangle），非常有意思。你取一个大三角形，在里面画一个倒着的小三角形，这就是它的规则。这么一画，你就得到了三个新的三角形。然后你对这三个新三角形再施加同一条规则。这就是递归：你对一个已经施加过规则的东西再施加一次规则，得到更小的三角形，如果一直做下去，它就无限地小下去。
凯莱赫： 这是计算它的一种方式，一种看待这条规则的方式。但我在讲义里用的是另一种，我在那里谈到了迭代函数系统（iterated function system）。我直接做给你们看，做完你们就明白它是什么意思了。
凯莱赫： 假设我们从一个点开始，比如这个点，任意一个点都行。我们有三种选择，这个玩法叫「混沌游戏」（chaos game）：把这个点移到它与顶点甲连线的中点，或者移到它与顶点乙连线的中点，或者与顶点丙连线的中点。假设我们选甲，那就走到这里，正好在中间。而在迭代函数系统里，我们把这件事一遍一遍地做下去，每次随机挑三个顶点中的一个，朝它走一半路。
凯莱赫： 那么，接下来我们走向这一个，到这里；再走向这一个的一半；再走这一个；再这一个；再这一个；再这一个。就这样一直随机地走下去，把每一步落下的点都画出来。我写的那个程序（讲义里有）做的就是这件事，它一直跑，一直画点。最后你得到的，就是谢尔宾斯基三角形。太疯狂了。图就在第八页。
学生： 也就是说，随机怎么选都无所谓？不管你怎么选，最后画出来的总是同一个样子？
凯莱赫： 是的。
学生： 那如果我把程序重新跑一遍，因为它是随机的，选的顺序就会不一样。
凯莱赫： 对，正是这样。重跑一次，它的选择会不同，也许第一次不是走向这个顶点，而是走向那个顶点，也许它连着朝同一个顶点走了十次、一百次。程序是随机挑的。他问的是：既然是随机的，是不是还会生成同样的图？答案是会。这真是让人叫绝。等我们做完下一个例子，也就是分形蕨，你们会理解得更透彻。
凯莱赫： 我们先快速看一眼代码，然后想一个问题：谢尔宾斯基三角形的这段代码，是递归的吗？代码里 def drawSierpinski 就是画三角形的那部分。A、B、C 是三个顶点，也就是这三个点。points 等于由 A、B、C 组成的列表。currentPoint 就随便设成 A 好了。while true 的意思是，这段代码反复执行，一直做下去，做无穷多次，直到你把程序停掉为止。里面写着 nextPoint 等于 pickFrom(points)，pickFrom 是上面定义的函数，作用就是从你给它的列表里随机挑一个。所以 pickFrom 正是那个随机决定走向哪个顶点的东西。
凯莱赫： 挑到点以后，就是 currentPoint.X 等于 (currentPoint.X + nextPoint.X) 除以二。你在做的其实是把当前点和目标点的 X 坐标取平均，X 和 Y 都这么做，得到的就是当前点与目标点的中点。这一句就干这件事。然后 image.fillPixel 把这个点画到屏幕上。第八页那张图，就是这个程序生成的。它就这样一直跑，一直画。
凯莱赫： 所以问题来了：这个东西是递归的吗？我们说过，递归函数是调用自身的函数。这个答案我们留到下一个例子之后再说。到这里有问题吗？
递归必须触底吗
学生： 能再说一遍递归的定义吗？
凯莱赫： 一般来说，递归就是用自身来定义自身的东西，是绕回到自身的东西。
学生： 那如果你反复施加那条递归规则，它不就会变回它一开始的样子吗？
凯莱赫： 不一定，因为每一次施加规则，都有一点微小的变化。以阶乘为例，它说的不是「n 的阶乘等于 n 的阶乘」，而是「n 的阶乘等于 n 乘以 (n-1) 的阶乘」。阶乘那一部分是递归的，但它并没有原封不动地绕回自身，中间有变化。
凯莱赫： 至少对递归函数来说是这样：函数被定义出来，然后调用自己。我不确定这能不能回答你的问题，但你设想一下，如果我们把这几行判断去掉，函数只剩下一句「def fib(n) 返回 fib(n-1) 加 fib(n-2)」，会发生什么？它会一直调用自己，无穷无尽地调用下去。这是个问题。所以，所有递归函数要想真正做成什么事，就必须在某一处触底。它们必须停下来，而停下来的机关就是这个条件：只有当 n 大于 1 时才继续；如果 n 小于或等于 1，就直接返回。这就把它止住了。这样回答你的问题了吗？你要是觉得没答上，可以再问一遍。
学生： 也就是说，只有计算机里的递归函数才需要触底？
凯莱赫： 是的，需要触底的是那些递归的计算机函数。递归还有别的种类。不过，自然界的递归其实最终也是要触底的。拿自然界的树来说，它分叉，分叉，再分叉，但最后总会走到一片叶子上，就不再分叉了。这棵树里面运行着某种递归的程序，而当枝条细到某个尺寸时，程序会收到某种信号，我想大概是这样，于是它转而长出一片叶子。所以这类递归过程也是会触底的。
凯莱赫： 但刚才那个谢尔宾斯基的程序确实是递归的，我们过一会儿会看到它为什么是递归的，而它并不触底，因为它就这样永远跑下去。
学生： 也就是说，如果你想让递归真正给出一个可见的结果，它就必须触底，否则你拿不到返回值。但你完全可以设想一个不触底的理论世界，让它一直延续下去。
凯莱赫： 对，完全正确，你概括得非常好。他的意思是：要得到递归的任何实际显现，它就必须触底，这样才能把结果交还给你。但你确实可以设想不触底的理论世界，让它一路延伸下去。侯世达在这一章前面的对话里就这么干了：一个精灵得去问元精灵，元精灵又得去问元元精灵。有人读过那一段吗？
学生： 读过，而且那一段里时间是越来越短的。
凯莱赫： 对，时间越来越短，所以最后你在无穷小的时间里重复了无穷多次。
学生： 是啊，太疯狂了。
凯莱赫： 真的很值得琢磨。虽然是纯理论的，但想一想非常有意思。
分形蕨与坐标变换
凯莱赫： 下一个是分形蕨（fractal fern），第九页，特别酷，也特别漂亮。
凯莱赫： 我要先讲一个概念：坐标变换（coordinate transformation）。假设在这个大矩形和那个小矩形之间有一个坐标变换。它是一个作用在点上的函数，作用在二维点上。比如你取这里这个点，对它施加这个变换，得到的就是那边那个点；再取这里的另一个点，施加变换，得到那边对应的点。小矩形里的图案，就是大矩形里的一个缩小的副本。
凯莱赫： 这就是「函数」，也就是迭代函数系统里「函数」的那一部分。「迭代」指的是你一遍遍地做下去，「系统」指的是这样的函数不止一个，而是有一批。在谢尔宾斯基三角形里是三个。
凯莱赫： 分形蕨是一个有四个函数的迭代函数系统。谢尔宾斯基那个有三个，那三个点每一个就是一个函数，「朝某个点走一半」就是一个函数。而蕨这个有四个函数，每一个都是一个坐标变换。比如这一个，是从外面这个大矩形到里面这个小矩形的坐标变换。如果我们取大矩形里的这个点，施加这个变换，就得到小矩形里的这个点。
凯莱赫： 假设我们取大矩形的中心点，施加一次变换，得到的是小矩形的中心点，大概在这里。但接下来我们要说：好，这个新点现在被看作是大矩形里的点，我们对它再施加一次变换。于是大矩形里的这个点，映到小矩形里大概这个位置。然后再说：好，这个点现在又是大矩形里的点，再施加一次。于是得到这里，这里，这里，一连串越来越小的点。它们最终会越缩越小，因为这两个矩形有一个角点是重合的，我想是这样，应该没错，是同一个点。
凯莱赫： 我们再看另一个变换。这个变换的目标是一条线段，你就把它当成一个压扁的矩形来想，它同样是一个坐标变换。我们把大矩形里的任意一点，映到这条线段上的某一点。大矩形里这个点会映到线段的顶端，这个点会映到线段的底端，中心点会映到线段的中点。
凯莱赫： 现在想象一个只有这两个函数的迭代函数系统。假设两个函数各有大约一半的机会被随机选中。不，我们换个设定：假设有百分之九十的时间施加第一个映射。那么从这个点出发，它会映到这里，再映到这里，只要一直施加这个映射，它就一路往上爬。但假设它爬了一百次以后，有一次选中了另一个映射，落到了下面。也就是说，它本来在最上面，一映射就回到这里重新开始，然后又往上，往上，往上。再假设走到某处时，计算机决定施加第二个映射，而它此刻大约在四分之三高的位置，那它就会落到线段四分之三高的地方。正因为是随机的，只要一直做下去，最终它几乎会把这条线段上的每一个点都填满。这一点很值得琢磨。到这里有问题吗？
四个映射与概率
凯莱赫： 现在回到蕨。四个变换全都是从外面这个大矩形出发，映到里面某一个较小的区域。比如取上面这个点施加这个变换，它会落到这里；取那个点，会落到那里。变换的走向大致就是这样。
凯莱赫： 假设我们的迭代函数系统就有这么几个。我们从大约一半高的位置出发，选中了这个映射，它落到这里，落到这块区域的中间。然后我们连续施加这个映射很多次，它一路往上爬。再施加一次那个映射时，它这次的位置更靠近顶端了，所以落点也更靠外、更靠近这个矩形的顶端。然后一次又一次地施加。也许有时候它只往上爬了一格，那落点就在下面这里。最终，它会用这个图案把整个矩形填满，长成这个样子。而由于这里面几乎每一个点都会被那个映射反复作用很多次，我们得到的就是这样一个蕨的结构。是不是特别酷？
学生： 你的意思是说，小的那一块里的所有点，会被映射到大的那一块的不同部位去？
凯莱赫： 你说的是谢尔宾斯基三角形还是蕨？
学生： 蕨。就是说小的那一块里有一堆点，那些点是不是分别对应着蕨的某一部分？看上去它们是被重复了，只是变小了，而且每一份里的点数量还一样多。
凯莱赫： 完全正确。
学生： 可是如果越缩越小，怎么可能塞进同样多的东西？
凯莱赫： 说得对，实际上塞不进。我举个例子。假设我们不是只对一个点施加变换，而是对一堆点施加，比如这条线上的所有点，或者接近所有的点。我们把这个映射施加若干次，得到这一批、这一批、这一批点。现在我们对所有这些点施加另一个映射，它们全都会映到这里来。然后我们再做一次，再做一次。这样一来，所有那些点最终都会被映到这一块里，于是你在这里就得到了整个结构的一个小副本，你有了这些小分枝。接着这一整块又被映到上面这里，于是又有了分枝、分枝、分枝。而由于这里已经有了更小的分枝，你就有了往下两层的结构。这整块东西连同新长出来的分枝，又会被映回这里去，随着迭代进行不断填充进来。
凯莱赫： 但它不会一味地往上爬。假设我们百分之百地施加那个往上的映射，它就只会一路爬上去，哪儿也不去。可如果我们只有百分之七的时间施加另外的映射，它就会爬到各种不同的高度，然后被映回下面，再往上爬，再被映回去。再加上从这一块到那一块的变换，我们得到的就是这个东西。它是递归的。它之所以递归，是因为这些映射最终映到了自身之上。
凯莱赫： 我们看看代码，它和谢尔宾斯基三角形的代码非常像。代码本身不是递归的，但映射是递归的，正是这一点让整件事成为递归。
凯莱赫： class fern，drawFern，while true，意思是这段一直执行，反反复复地做。然后从这一列变换里随机挑一个。第一个写着「映到茎」，意思是从整体映到这里，映到茎上。第二个「映到左枝」，从整体映到这一块。第三个「映到右枝」，映到下面这里。第四个则是从这里映到这里，就是往上那么一走。
凯莱赫： 紧接着，代码里写的是：从一个函数列表里挑，同时给出一个概率列表：0.01、0.07、0.07、0.85。这就是这四个映射被选中的概率。如果你让它们等概率，那么「往上」这个映射连续发生超过五次左右的机会就非常小，于是点只会爬一点点就被映回去，得到的分形会非常稀疏，绝大多数点都堆在下面这里，看上去很难看。我试过。真希望能当场写给你们看。所以，0.01 表示映到茎的情况占百分之一，映到左右两条分枝各占百分之七，而往上盘旋的那个映射占百分之八十五。
凯莱赫： 现在休息十分钟。还有问题吗？
代码不递归，映射递归
凯莱赫： 我们继续。在离开迭代函数系统之前，我想指出一点：从映射的角度看，谢尔宾斯基三角形和蕨其实是同一回事。谢尔宾斯基三角形有三个映射，一个把大三角形映到这个小三角形，一个映到那个小三角形，还有一个映到第三个小三角形，三者被选中的概率相等。
凯莱赫： 你想一想就明白了：从任意一点朝某个顶点走一半，本质上就是把它映到某个小三角形里去。假设你有这么一条线上的所有点，对它们施加这个函数，结果就是把它们整体映到那个小三角形里去。所以这些三角形是递归地映到自身之上的。这里确实有递归在发生，只不过递归不在代码里。代码本身只是在重复，但它重复的东西，正是这些自我映射的递归映射。
学生： 这么说，同一个算法总有不止一种表达方式？
凯莱赫： 同一个算法总有不止一种表达方式。是的，非常有意思。尤其是在分形这类东西上，好像总还有另一条路可以走，得到同样的结果。谢尔宾斯基三角形在这一点上尤其惊人。
跳出系统
学生： 那如果代码里根本没有递归函数呢？在不运行代码的情况下，你怎么判断它的输出会是递归的？
凯莱赫： 你是说，你手上有代码，但它里面没有递归函数？
学生： 对，代码里没有递归函数。如果你不能运行它，你怎么在不跑一遍的情况下发现输出会是递归的？
凯莱赫： 他问的是：既然代码本身不是递归的，你怎么知道输出会是递归的，哪怕里面一个递归函数都没有。我的看法是这样：当你写代码的时候，如果你意识到代码做的事情是在施加这些二维映射，你就可以在脑子里推演：这些映射会以某个概率被反复施加，那么结果会是什么。你只要在头脑里做这个外推，其实就是在跳出系统（stepping out of the system），你在问：这东西究竟在干什么？
学生： 可是非得那样不可吗？就不能待在系统里面判断？
凯莱赫： 待在系统里面？在这里，待在系统里面就意味着真的去运行代码，像计算机执行程序那样一步步走。而跳出系统，我指的是从更高的层面去看正在发生的事。
学生： 也就是说，当你把那些细节抽象掉，把做着同一件事的东西归到一起，你就得到了一个更高的层面，而递归其实是在那个层面上发生的。
凯莱赫： 完全正确，就是这样。他说的是：当你把这些函数具体在做什么的细节抽象掉，你就开始察觉到一个更高层面的东西，而那个东西本身就是递归。所以，只要你的思考抽象到足够的程度，你就能靠逻辑判断出它会生成一个递归的形状。
学生： 可是并没有什么简单的算法或者程序，能替你判断一段代码是不是递归的吧？
凯莱赫： 你是说某种检测程序？
学生： 对，某种检测。
凯莱赫： 没有，你只能靠想。这正是人能做而机器做不了的事。没有哪种严格的检测可以施加到一段计算机程序上，然后告诉你它会不会产生递归的结果。因为在这个例子里，代码里根本没有递归函数，所以计算机无从知道，它没法问自己「我能不能抽象一层看看」。只有人能做这件事，至少目前是这样。而且这段程序也不是以映射系统的形式写出来的，它就是一些普通的函数而已。
凯莱赫： 所以你只要顺着映射、映射、再映射地想下去：你把这里的东西映到那边，原先在这里、可以无限往下延展的全部结构，现在就整个装进了那个小三角形的一个小角落里。这就是一个递归结构。
凯莱赫： 我们进入下一个例子，曼德博集合，非常有意思。既然设备现在通了，我想先把讲义里的程序跑一下，让你们感觉一下。先跑递归转移网络这个，看看会怎么样。它会生成一百个句子，因为代码里有一句打印语句执行一百次。第五页上写着 (0..100).each { println fancyNoun() }，这只是 Groovy 语言里一种花哨的写法。糟糕，跑不起来。算了，我一边讲一边试着修。这台机器我折腾了一整天了。
曼德博集合
凯莱赫： 下一个也是最后一个例子，是曼德博集合（Mandelbrot set）。你们大概都听说过它，非常有名，也许是所有分形里最有名的一个。它叫这个名字，是因为曼德博这个人极其热爱分形，努力把分形的概念传达给全世界，而这确实是一个了不起的分形。接下来会稍微数学一点，不过没关系。
凯莱赫： 它活在复平面上。也就是说，我们有这样一个平面，横轴是实数，纵轴是虚数，我想是这么摆的。曼德博集合由这个函数定义：Z = Z² + C。先说清楚，一个复数就是这个平面上的一个点。假设这个点，纵坐标是 B，横坐标是 A，那么这个点就写作 A + Bi，而 i 是 -1 的平方根，这在现实中并不存在，所以它才叫「虚」数。两个复数相乘并不那么简单，你得老老实实把乘法展开，得到 AC 加上一堆项。我就不全展开了，会花不少时间。总之你得到的是一种并不线性的映射，它会怎么走并不容易预料。
凯莱赫： 算法是这样运作的：你在复平面上取一个点，C 就取这个点的值。而 Z 从零开始，就是零加零 i。然后你反复施加这个函数。第一次施加：Z = Z² + C，0 的平方是零，加上 C，所以第一次迭代之后，Z 就等于 C，Z 落在这里。然后再施加一次，这次的 Z 已经是刚才得到的新 Z 了。Z = Z² + C，你先做平方，再加上 C 的实部和虚部，于是这个点就被映到了别的地方，比如这里。然后你一次又一次地施加：这里，这里，这里。我不知道我讲得是不是太快了。总之施加一次得到这个点，它成了新的 Z，然后这个新的 Z 又绕回去，我们再算 Z² + C。C 永远是最初那个点，变的只是 Z。它映到这里，新的点又成了 Z，再算一次 Z² + C，又映到那边去。我写了一个小程序，可以把这个映射过程和它的形状演示出来。
学生： C 可以取在任何地方吗？还是说 Z 可以？就是起点。
凯莱赫： 起点可以取在任何地方。但真正运行算法时，我们只在 -2 到 2 这个范围里取，因为只有在这个区域里，这个分形才有有趣的事情发生。
凯莱赫： 算法我还没讲完。假设有一个点在这里，非常靠近原点，那么随着迭代，它往往会向内盘旋。而外面这个点，尤其是落在半径二之外的点，施加这个函数以后，往往会被甩到这里，再甩到那里，越跑越远。所以，我们渲染曼德博集合的做法是：施加函数若干次，如果这个点最终跑出了以原点为心、半径为二的圆，就停止迭代，因为我们知道，一旦它出去了，就会一路跑到无穷远。它逃逸了。这就叫逃逸迭代次数（escape iterations），也就是跑出这个圆所需要的迭代次数。
凯莱赫： 然后我们根据逃逸迭代次数给这个点上色。另一半规则是：如果它永远不逃逸，我们就把它涂成黑色。而要真正判断这一点，我们的办法是固定迭代若干次，比如五百次，或者七十次，如果迭代这么多次之后它还没有逃逸，我们就姑且认为它永远不会逃逸了。这当然不严格。所以我们画出来的只是真实集合的一个近似，但要渲染出图来，就只能这么做。这类点涂黑。
凯莱赫： 真正渲染的时候，我们遍历屏幕上的每一个像素，对每个像素执行这套算法。这个点就是 C，我们迭代，检验，迭代，检验，迭代，检验。检验的内容就是它是否跑到了圆外。一旦跑到圆外，就按照所用的迭代次数给它分配一个颜色。每一个像素都这么办。比如这一个点，它会向内盘旋，其实它不是一条连续的线，只是不断施加函数得到的一串点，向内盘旋，永远不会逃逸，所以我们把它涂成黑色。
凯莱赫： 这个小程序把这一切演示得非常好。我用 Java 实现了这套算法，它会把每一步的点输出出来，并在相邻的点之间连线。比如从这里出发，画到这里，这里，这里。
凯莱赫： 结果就是我们看到的这幅图。我把鼠标移来移去，它就在做这些检验。这里只需要一次迭代，一次迭代对应浅蓝色。这里是两次，上面会列出来，一、二。所以凡是这个颜色的地方，点在跑出圆外之前只经过了两次迭代。往里走一点，就需要三次，四次，五次，六次，七次，越往里迭代次数越多。所有有颜色的点最终都会逃逸，而所有黑色的点不会。里面那些图案特别有意思。你看中间这些，就是一路向内盘旋。这边这些呢，有一种循环的模式，看到了吗？函数绕回到了自身，所以它有点像是递归的。我也说不太清它究竟怎么个递归法，但它确实有那个味道。再往外走到第二个瘤状凸起上，形状就更漂亮了。
凯莱赫： 我们还可以放大。它会重新计算，此刻它正在为每一个点重算这套算法，速度非常快。于是我们能看到这些生成分形的极漂亮的形状，简直疯了。
凯莱赫： 我们在这里确实能看到递归，看上去肯定有某种递归的东西在运作。而递归的部分在于，Z 被施加到了自身上：第 n 个 Z 等于前一个 Z 的平方加 C，然后这个 Z 又被重新当作旧的 Z。这种重新框定、重新施加函数的动作，正是它的递归所在。所以这说得通。黑色区域里的点，就是无限地递归下去。代码本身不是递归的，但映射函数还是那个递归的东西。真正的曼德博集合其实只有那些黑点，其余的点我们上色，只是为了好看。
凯莱赫： 我们快速看一下代码。def drawMandelbrot，看到了吗？window.set(-2, 2)，这是把绘图范围设定在这个区间。然后对窗口宽度上的每一个 X 像素、高度上的每一个 Y 像素，C.real 和 C.imaginary 取屏幕上对应的 X、Y 值。这一步的意思是，让像素对应到我们所处理的那个空间，也就是复平面上的实际点。接着 def iterations 等于 calculateIterations(C)，我们把 C 传进去。记住，这就是 C，起点就是 C。然后 def color 等于 calculateColor(iterations)，我们根据逃逸所用的迭代次数算出颜色。最后把这个像素填成那个颜色，画到屏幕上。
凯莱赫： 再看 calculateIterations 函数。int calculateIterations，这个写法表示它会返回一个整数，参数是一个复数 C。Z.real 和 Z.imaginary 都从零开始，就从那里起步。iterations 也从零开始，我们要数一数用了多少次迭代。然后：只要圆还包含着 Z（这是另一个函数，专门检验点是否在圆内），并且迭代次数小于最大迭代次数，就继续。最大迭代次数就是那个界限，超过它我们就认定这个点会一直向内盘旋、老老实实待在里面。
凯莱赫： 只要这些条件成立，就执行 Z = Z*Z + C，也就是 Z 的平方加 C。之所以能这么写，是因为我为复数重载了乘法和加法运算符，所以它的行为是正确的，会去做那套古怪的复数乘法。做完之后 iterations++，也就是迭代计数加一。而 calculateColor 就是根据迭代次数算出颜色。
巴赫的嵌套和声
凯莱赫： 我们还剩二十分钟。我想用音乐和分形把你们震一震。我要放三段巴赫，它们都太棒了。第一首其实不是约翰·塞巴斯蒂安·巴赫写的，它是《小和声迷宫》（Little Harmonic Labyrinth），书里那篇对话正是以这首曲子为蓝本的，作者是卡尔·菲利普·埃马努埃尔·巴赫。
凯莱赫： 英语有一套语法，我们可以把句子嵌进句子里，再往里嵌更多的句子，我们还可以再嵌，而刚才这句话本身就是一个嵌套的句子。音乐也一样，它也有自己的语法。那些和弦进行、旋律，尤其是和声，构成了一种语言，可以在不同的调之间移动。这就是巴赫把递归嵌进音乐的一种方式：他有这些嵌套的和声结构，嵌套的和弦进行。书的第五章里谈过这件事，而那篇对话正是照着我们刚听的《小和声迷宫》写的。
凯莱赫： 旋律同样可以带有递归，因为它可以有模式。比如这个主题，巴赫经常这么干：他拿一个主题，配上不同的和声重述一遍，而且他会把它嵌进大大小小不同的尺度里。举个例子，我不确定他在这一首里是不是这么处理的，但在更大的尺度上，整体的和声走向本身可能也遵循着同一个主题的形状：在一段很长的时间里停在这个调上，又在一段很长的时间里停在那个调上；而当他身处那个调里的时候，他弹的又是这个主题。这就是嵌套的例子。
凯莱赫： 所以严格说来，这里并没有递归本身，有的是递归的结果。这就是递归过程和递归结构的区别。递归结构基本上就是任何带有嵌套的结构。英语是一种递归结构，因为它出自一套递归语法，它有嵌套。音乐也是递归结构，而不是递归过程。
学生： 那么递归过程差不多就是一个函数，它规定了你怎样得到那个递归结构？
凯莱赫： 正是如此。他说，递归过程有点像一个函数，规定了你如何最终得到一个递归结构。完全正确。
学生： 所以他弹的是这样：整体上有一个大主题，他从这个主题里挑出一些片段来弹，弹着弹着离开那一段，转到另一段，而那一段同样属于这个主题。
凯莱赫： 对，正是这样。不过这一点很难听出来。
学生： 是很难听出来。
凯莱赫： 要听出这个，需要一副相当精细的音乐耳朵。
调用栈的压入与弹出
凯莱赫： 看看还剩多少时间，三分钟。我们来说说栈的压入和弹出。假设有一个函数叫 foo，它内部调用了函数 bar，这里是 bar 的定义，bar 做了一些事，又调用了 G，做了另一些事，这里是 G 的定义，G 也许只做一件事就结束了。于是你就有了一个调用栈（call stack）。其实任何具有这种递归式流程的语法里都会出现这种情况。所以，在计算机程序里，在英语里，都有「栈」这个概念。你在这里做一些事，做一些事。
凯莱赫： 当你调用 bar 时，你的注意力其实转移到了那边，转到了 bar 上。但你在心里，或者说在计算机的内存里，保留着你刚才在哪儿、从哪儿离开的记录。
学生： 这是不是就像你想做成某件事的时候，比如你手上有好几首曲子之类的？
凯莱赫： 你是说调用？
学生： 是目标。你有目标。
凯莱赫： 对，正是这样。这也正是编程之所以难的原因：你有一个高层次的目标，但要达成它，就像你说的，你得先达成另外一些目标，而那些目标每一个又需要更下层的目标。所以它其实是递归的，很疯狂。
凯莱赫： 那么，这个程序执行的时候，它先做完这里的事，把当前位置（就叫位置 A 吧）压到栈上。这就是栈，上面现在有 A。然后它进入 bar，做完那一堆事，接着调用 G。为了记住这次是从哪儿走的，我们把这个位置叫做 B，把 B 压到栈上，然后进入 G，做完 G 里的事。做完之后 G 返回。返回的时候它要问：我上一次是在哪儿？栈就是干这个用的。我上一次在哪儿？在 B。于是我们弹出。把东西放到栈上叫压入（push），从栈上取下来叫弹出（pop）。我们弹出，说：好，这是 B，B 就是我们刚才所在的地方。于是回到那里，把 bar 剩下的部分做完。做完之后再问：我们上一次在哪儿？取出 A，回到 A，把 foo 做完。
学生： 所以你也可以让那些东西对应到别的事物上，对吧？比如乐曲的不同段落。而那个东西又在某种意义上反映着它自己。
凯莱赫： 对，当然可以，正是如此。所以，与《小和声迷宫》相对应的那篇对话就具有这样的结构：进入一层，再进入另一层，然后退出来，再退回上一层。
凯莱赫： 五点了，今天就到这里。
排版 + 横图 + 来源，粘贴即成稿
章节 · 点击跳转视频
0:00
开场：阶乘与斐波那契的递归定义
6:54
GEB 递归转移网络：语法生成句子
10:54
递归画树：分枝、深度与终止
16:04
科赫曲线与随机化的海岸线
20:10
有限面积无限周长：英国海岸线之问
26:21
谢尔宾斯基三角形与混沌游戏
32:16
递归为何必须触底：学生问答
36:43
分形蕨：迭代函数系统与坐标变换
49:06
代码不递归但映射递归：跳出系统
56:07
曼德博集合：复平面与逃逸迭代
69:28
巴赫的嵌套和声：递归结构与过程
72:49
调用栈的压入弹出与音乐迷宫
本期小问 · 档案清单
26:21
一条简单规则反复施加，怎么长出无限复杂的图形？
49:06
代码里没写递归，递归还会藏在哪一层？
20:10
有限的面积为什么能被无限长的边界围住？
69:28
句子套句子和巴赫的和声嵌套，是同一回事吗？
本期讲者
柯伦·凯莱赫MIT 2007 年夏季《哥德尔、埃舍尔、巴赫》研讨课的代课讲者，本讲用自己编写的 Groovy/Java 程序演示递归与分形。后成为数据可视化领域的开发者与教育者。
学生课堂上的 MIT 学生，多次提问（科赫雪花剪断比喻、海岸线是否收敛、无递归函数如何判断输出递归等），推动了讲者对递归定义的深化。
01开场：阶乘与斐波那契的递归定义
0:00
The following content is provided under a Creative Commons license. Your support will help MIT Open Courseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT Open Courseware at ocw.mit.edu. So, my name's Curran Kelleher. I'll be lecturing today about recursion and fractals. Justin Curry's not here today. So, I'm going to fill in. So, um today I'm going to just do a bunch of example programs, computer programs that are recursive. Some of them don't make pictures and some of them do. And when they make pictures, they're fractals.
以下内容基于知识共享许可协议提供。您的支持将帮助 MIT 开放课程继续免费提供高质量的教育资源。如需捐赠或查看数百门 MIT 课程的更多资料，请访问 MIT 开放课程网站 ocw.mit.edu。我叫 Curran Kelleher。今天由我来讲递归和分形。Justin Curry 今天不在，所以我来代课。那么，今天我打算演示一堆示例程序，都是递归的计算机程序。有些不会画图，有些会。而当它们画图的时候，画出来的就是分形。
0:40
Frac- fractals are things that are self-similar at different scales that you can zoom in on. Um we're going to take a break at 4:00 for 10 minutes. And then towards the end, hopefully, I'll show you a bunch of examples of fractals and play some Bach music. So, first of all, um let's consider um a recursive mathematical function, uh factorial. Uh something factorial, like three factorial is 3 * 2 * 1. Four factorial is 4 * 3 * 2 * 1. So, like and this this is factorial, the exclamation point.
分形是那种在不同尺度上都自相似的东西，你可以不断放大去看。我们会在 4 点休息 10 分钟。然后接近尾声的时候，希望我能给你们看一堆分形的例子，还会放一些巴赫的音乐。首先，我们来看一个递归的数学函数，阶乘。比如某个数的阶乘，3 的阶乘就是 3 × 2 × 1。4 的阶乘就是 4 × 3 × 2 × 1。这就是阶乘，写成一个感叹号。
1:24
So, um the way this is defined is actually recursive. So, if you take anything factorial, say n, factorial is n minus 1 factorial. Um say Let's say n is four, and then n minus 1 would be three. So, four factorial is Wait. n Yeah, times n. So, it's going to be Well, n n times n minus 1 factorial. So, four is n times this whole thing is three factorial. It's n minus 1 factorial. So, this is a recursive definition. And if you look in the handout, um I wrote a little computer program on page three, I think, that that does the factorial. So, it goes like this.
它的定义其实是递归的。所以如果你取任意一个数的阶乘，比如 n，n 的阶乘就是 n 减 1 的阶乘……比如说 n 是 4，那 n 减 1 就是 3。所以 4 的阶乘是……等一下，n……对，乘以 n。所以应该是 n 乘以 n 减 1 的阶乘。所以，4 就是 n，而这一整块就是 3 的阶乘。也就是 n 减 1 的阶乘。所以这是一个递归定义。如果你看讲义的话，我在第三页写了一个小程序，我记得是第三页，就是算阶乘的。它是这样的。
2:40
So, just some for you for those of you who don't know much about programming, uh def means define. So, we're defining a function called factorial. And it takes as an argument n. So, you can call this function, pass it a number. And inside the function, it's referred to as n. So, fact this factorial function says if n is greater than 1, return n times factorial of n minus 1.
为了照顾那些不太懂编程的同学，def 的意思是 define，定义。所以我们在定义一个叫 factorial 的函数。它接受一个参数 n。你可以调用这个函数，传给它一个数字。在函数内部，这个数字就叫 n。所以这个 factorial 函数说：如果 n 大于 1，就返回 n 乘以 factorial(n - 1)。
3:19
Else, return 1.
否则，返回 1。
3:29
So, what makes this function recursive is the fact that it calls itself. Factorial is defined as n times factorial of something else. So, a recursive function is a function that calls itself. Um So, let me give an example. So, if if n is five, say, um the way we call this is we say factorial of five. So, when we when we say this, it calls this function and gives n the number five. So, it's what it's going to do is n is going to be five. So, n is greater than 1, so we return n times factorial of n minus 1.
让这个函数成为递归的，正是它调用自身这一点。factorial 被定义为 n 乘以另一个factorial。所以，递归函数就是调用自身的函数。嗯，我举个例子。假设 n 是 5，我们调用的方式就是写 factorialof five。所以当我们这样写的时候，它就调用这个函数，并把 5 传给 n。那它会做什么呢？n 等于 5。n 大于 1，所以我们返回 n 乘以 factorial(n减 1)。
4:18
So, say we're doing this algorithm, uh five is n. So, we're going to return five times factorial of n minus 1. So, we call factorial with the value four. And uh that's also greater than 1. So, we return four times factorial three. So, five times uh four times factorial three. So, we loop we call itself uh a bunch of times until we get down to 1.
假设我们执行这个算法，n 是 5。那我们就返回 5 乘以 factorial(n 减 1)。也就是用 4 这个值去调用 factorial。而 4 也大于 1。所以我们返回 4 乘以 factorial(3)。于是就是 5 乘以 4 乘以 factorial(3)。所以我们就这样循环，它不断地调用自己，直到降到 1 为止。
4:57
So, that's what actually ends up happening. This is recursion. So, another simple example, which is sort of like the factorial, is um the Fibonacci numbers, Fibonacci sequence. Uh
这就是实际发生的过程。这就是递归。另一个类似阶乘的简单例子，就是斐波那契数，斐波那契数列。呃……
5:19
So, the Fibonacci numbers, um it goes 1 1 and then the next one, you add the first two together. So, it goes 1 1 2. 1 + 2 is 3. 2 + 3 is 5. And so on. 8 Blah blah blah. These are the Fibonacci numbers. So, this is a recursive definition. Uh let's say this is
斐波那契数是这样的：1、1，然后下一个就是把前两个加起来。所以是 1、1、2。1 加 2 等于 3。2 加 3 等于 5。以此类推，8，等等等等。这些就是斐波那契数。这是一个递归定义。呃，我们说这个是……
5:53
These This is like the number of the element. Like, they're just numbers, index indices, if you will. So, Fibonacci of two is Fibonacci of zero plus Fibonacci of one. And so, Fibonacci five is going to be Fibonacci of three plus Fibonacci of four. So, generally, Fibonacci of n is going to be Fibonacci of n minus 1 plus Fibonacci of n minus 2. So, we could say that here. Instead of factorial, we call it Fibonacci. And we'll notice that like they're almost the same thing. I'll say fib. If n minus if if n is greater than 1, we return
这些……这个相当于元素的编号。就是一些数字，索引，如果你愿意这么叫的话。所以 Fibonacci(2) 等于 Fibonacci(0) 加 Fibonacci(1)。那么 Fibonacci(5) 就等于 Fibonacci(3) 加 Fibonacci(4)。一般来说，Fibonacci(n) 就等于 Fibonacci(n 减 1) 加 Fibonacci(n 减 2)。我们可以在这里这样写。把 factorial 换成 Fibonacci。你会发现它们几乎是一样的东西。我就写成 fib。如果 n 减……如果 n 大于 1，我们就返回
6:44
Fibonacci of n minus 1.
Fibonacci(n 减 1)。
02GEB 递归转移网络：语法生成句子
6:54
And this gives us the Fibonacci numbers, actually. Um so, it makes sense to you guys? So, on the in the handout, there are some example outputs of both of these, and you can see that's what happens. So, um who has their copy of Gödel, Escher, Bach today? So, if we will look on page 132 of Gödel, Escher, Bach. Oh, no, no, I can't look at it. Oh, well. 132 of Gödel, Escher, Bach has these two diagrams that are recursive tran- transition networks. They define a grammar, like sort of like English. It's not in English, it's not complete. It's It's a simplified version of English, but it he communicates the essence of the the notion of a grammar, a recursive grammar.
这实际上就给出了斐波那契数。嗯，大家听明白了吗？在讲义上有这两个程序的一些示例输出，你们可以看到就是这样的结果。那么，今天谁带了《哥德尔、埃舍尔、巴赫》这本书？我们来看《哥德尔、埃舍尔、巴赫》第 132 页。哦，不不，我看不了。算了。《哥德尔、埃舍尔、巴赫》第 132 页有两幅图，是递归转移网络。它们定义了一种语法，有点像英语。不是英语，也不完整，是英语的简化版本，但他传达出了语法——递归语法——这个概念的精髓。
7:50
So, you'll notice that um It's hard to do it in my head. Fancy noun, one of the nodes calls fancy noun again. It loops back out on itself. So, this is where the recursion is. So, what I did is I took this this diagram and wrote a little computer program that um whenever there's a choice of the transitions, it chooses one of those transitions at random. And um this is the program I wrote. I think it's on page five of my handout. So, if you look at that, um Yeah, I wish I had the projector. It's unfortunate.
你会注意到，嗯……在脑子里想这个有点难。fancy noun（花式名词），其中一个节点又调用了 fancy noun 自己。它绕回到自身。这就是递归所在。于是我做的事情就是，我把这幅图拿过来，写了一个小程序。每当有多个转移可以选择时，它就随机选一条转移路径。嗯，这就是我写的程序。我想它在讲义第五页。如果你看那个，嗯……唉，真希望我有投影仪，太可惜了。
8:32
Um Actually, can I look at the diagram? So, if you look at fancy noun, we begin and it calls ordinate noun. And then if you look at the program in the handout, um you find fancy noun. It's sort of halfway down, it says the RTN for fancy noun. Fancy noun equals And this is a function call. Well, first of all, fancy noun equals When you put curly braces around something, it it makes it a function, pretty much. So, fancy noun equals uh and and it copies pretty much directly from the diagram. Ordinate noun, which is also a function call, which is defined above, plus I'm still I'm back in fancy noun.
嗯，我能看一下那幅图吗？如果你看 fancy noun，我们从起点开始，它调用 ordinate noun。然后你看讲义里的程序，嗯，你会找到 fancy noun。大概在中间偏下的位置，写着「fancy noun 的 RTN」。fancy noun 等于……这是一个函数调用。首先，fancy noun 等于……当你在某个东西外面加上花括号，基本上就把它变成了一个函数。所以 fancy noun 等于……呃，它基本上是直接从图上抄下来的。ordinate noun，这也是一个函数调用，在上面已经定义过了，加上……我还在讲 fancy noun。
9:29
So, ordinate noun plus pick from preposition or relative pronoun or nothing. And if you look at the diagram in Gödel, Escher, Bach, the arrows coming out of ordinate noun point to relative pronoun, nothing, the end, and preposition. So, you can make this into a computer program, which is which is what I did. So, if you look at my program for a little while, you'll notice that all the arrows in the diagrams correspond to function calls in the in the program. And they're recursive because they eventually loop back on themselves.
所以是 ordinate noun 加上从 preposition（介词）、relative pronoun（关系代词）或者「什么都没有」里面选一个。如果你看《哥德尔、埃舍尔、巴赫》里的那幅图，从 ordinate noun 出来的箭头指向 relative pronoun、「什么都没有」、结束，还有 preposition。所以你可以把它写成一个计算机程序，我做的就是这件事。如果你花点时间看我的程序，你会发现图里所有的箭头都对应着程序里的函数调用。在程序里对应函数调用。而它们是递归的，因为它们最终会绕回到自身。
10:10
So, here Paul Stetson is trying to communicate the fact that languages themselves are defined by recursive grammars. This is why we can nest sentences inside of each other. It's recursive. So, recursion leads to nesting and sometimes infinite nesting. And that's what That's where fractals come from. So, right after this program in the handout, there's a sample output. So, just read through some of those sample outputs. They're They're pretty pretty funny. I have an old version. Can I look at someone's handout just to read? Just a handout.
所以在这里，Paul Stetson 想传达的是：语言本身就是由递归语法定义的。这就是为什么我们可以把句子嵌套在句子里面。这是递归的。所以递归会导致嵌套，有时候是无限嵌套。分形就是从这里来的。讲义里这个程序后面就有一段示例输出。大家读一读那些示例输出。挺挺有意思的。我手上是旧版本。我能看一下谁的讲义读一下吗？就借一下讲义。
03递归画树：分枝、深度与终止
10:54
So, small small bagel inside the strange cow. Uh it's sort of It makes sense as an English sentence and it was generated by this computer program. So, I think that's just fascinating. But of course, some of them don't make sense like large small bagel that runs large small large horn. Like, it just doesn't make any sense. So, next example. Uh let's see. So, the next example on page five, I think, is a tree. We're going to make a tree picture using recursive functions. So, I'm going to uh
「奇怪的牛肚子里的小小百吉饼。」呃，它作为一个英语句子还算说得通，而且是这个计算机程序生成的。我觉得这真是太迷人了。当然，有些就说不通了，比如「跑动着的大的小的百吉饼大的小的大的号角」。就是完全讲不通。那么，下一个例子。呃，我看看。第五页上的下一个例子，我想是一棵树。我们要用递归函数画一幅树的图。那么，我要，呃……
11:41
I'm going to write some pseudo code. It's not real code. It's sort of pseudo code to communicate the idea of what this program is doing.
我要写一些伪代码。不是真正的代码，是伪代码，用来传达这个程序在做什么的思路。
12:04
So, we have a function that grows a tree. It starts from a single branch. And I'll do it at that one here. This is like the starting point. This is the entry point. So, it says all right, class, all this stuff, tree tree parenthesis parentheses. That gets called when the program starts. So, this function call, grow tree, 0.50, trunk height, all this stuff is this first one. This is what initiates the process. And then what the function does is um pretty much if the depth is greater than zero. Um
我们有一个函数，用来长出一棵树。它从一根树枝开始。我在这里画一下。这就像是起点，是入口点。所以它说，好，class，所有这些东西，tree tree括号括号。程序启动的时候就会调用它。所以这个函数调用 grow tree、0.50、trunkheight，所有这些东西，就是第一根。这就是启动整个过程的东西。然后这个函数做的事情，嗯，基本上就是如果深度大于零。嗯……
13:16
So, this tree function uh calls itself twice, once for each branch. So, the first time the program calls this function it makes this. It draws it on the screen. So, notice um here it it adds the actual line. If If you look at the the the code that it says add new JV line X1 X2 that stuff. That actually adds a line to the screen. I wish I could you know, show you the actual code running, but I can't cuz So, this is the first time. And then depth is the number of times it's going to branch out. And so, depth is 11. It's going to make a big tree.
这个 tree 函数呃，会调用自己两次，每根分枝调用一次。所以程序第一次调用这个函数时，画出的是这个。它把它画在屏幕上。注意，嗯，这里它加上了实际的线条。如果你看那段代码，写着 add new JV line X1 X2 之类的。那实际上就是往屏幕上加一条线。往屏幕上加。真希望我能给你们演示代码实际运行的样子，但我做不到，因为……所以这是第一次。然后depth 就是它要分枝的次数。depth 是 11，那就会长成一棵很大的树。
14:09
Um What it's going to do is make two sub branches. Says grow tree This this one corre- correlates to this one here. And this one corresponds to this one here. And uh if you look at the code in the handout, it says grow tree X2 Y2. X2 Y2 is the end point of the previous branch. Root length times size factor. is a factor by which it's going to scale them. So, this would be like maybe half the size or 0.7 of size factor is 0.58, so it's about half the size. And root angle plus angle factor, root angle minus angle factor. These are in the two grow tree function calls.
嗯，它要做的是长出两根子枝。写的是 grow tree……这一个对应这里这一根。这一个对应这里这一根。呃，如果你看讲义里的代码，写的是 grow tree X2 Y2。X2 Y2 是前一根树枝的终点。root length 乘以 size factor。这是缩放的比例因子。所以这根大概是一半的大小，或者 0.7……size factor 是 0.58，所以差不多是一半大小。还有 root angle 加 angle factor、root angle 减 angle factor。这些在那两个 grow tree 函数调用里。
15:02
Angle factor, which is point well, pi over four. It's exactly 45°. So, each time it branches, the the the the two branches are going to branch out at that angle. And so, here say say we do depth of four when you call it the first time. The depth here is going to be four. And then you pass into the function depth minus one. So, here inside inside the function that's generating this, depth is going to be three. And so, it's going to keep going down until depth is zero. So, here depth is well, depth is four.
angle factor 是 0.……嗯，是 π 除以 4。正好是 45 度。所以每次分枝的时候，那两根枝就会按那个角度岔开。那么在这里，假设我们第一次调用的时候 depth 是 4。这里的 depth 就是 4。然后你传进函数的是 depth 减 1。所以在生成这个的函数内部，depth 就变成 3。它会一直往下走，直到 depth 等于零。所以这里 depth 是……嗯，depth 是 4。
15:45
Three. Two. One. And it does it on this side, too.
3。2。1。这一边也是一样。
04科赫曲线与随机化的海岸线
16:04
So, it just keeps going like this. This is This is a fractal. And you could imagine if you were to continue this infinitely like instead of saying depth of 10 or 11, just say depth of infinity. Say theoretically, if we could do this uh this this shape could be zoomed in on infinitely, forever. And this is the notion of a fractal. And it would look the same as it does on the on the large scale. So, any questions about the tree? So, next we're going to do a the Koch curve. Koch curve is sort of similar to the tree except that the rules are different.
所以它就这样一直进行下去。这就是一个分形。你可以想象，如果你无限地继续下去，不说深度 10 或 11，而是说深度无穷大。假设理论上，如果我们能做到，这个形状可以被无限地放大，永远放大下去。这就是分形的概念。放大后它看起来会和大尺度上一模一样。那么，关于树的部分还有什么问题吗？接下来我们要做的是科赫曲线。科赫曲线和树有点类似，只不过规则不一样。
16:50
So, first con- conceptually, this is what a Koch curve is. You start with a line or in some cases a triangle to make make the whole thing. And you divide it into three parts. And then you make an equilateral triangle. I mean, the sides are all the same. Out of the thing in the middle. And get rid of this line. So, this is the rule. Go from a line to this thing. And then this rule is applied to each one of these segments. So, you go like this. And so on. Like to each of these smaller segments. So, the fact that like the simple rule is being applied to something over and over again.
首先从概念上讲，科赫曲线是这样的。你从一条线段开始，有时候是从一个三角形开始，来构成整个图形。然后你把它分成三段。接着你做一个等边三角形。我是说，各边长度都相同。以中间那一段为基础做出来。然后把这条线去掉。所以这就是规则：从一条线段变成这个东西。然后这个规则会被应用到这些线段中的每一段上。所以你会得到这样。以此类推，对每一段更小的线段都这样做。所以，正是因为这个简单的规则被一遍又一遍地应用到某个东西上，
17:35
And the thing it's being applied to is the result of the previous execution of the rule makes it recursive. So, you could keep drawing it. Let's look at the actual code, the program. Um It says Koch. I think it's on page seven. So, let's see let's see, create curve.
而且被应用的对象是上一次执行规则的结果，这就使它具有递归性。所以你可以一直画下去。我们来看看实际的代码，这个程序。嗯，上面写着 Koch。我想是在第七页。那我们看看，create curve（创建曲线）。
18:12
What create curve does essentially is call itself four times.
create curve 本质上做的事，就是调用它自己四次。
18:26
And each of those four times corresponds to this one, this one, this one, and this one.
而这四次分别对应这一段、这一段、这一段，还有这一段。
18:39
Um So, yeah, let's look at the actual code. You see these four function calls to create curve in the middle there? X1 Y1, AX, AY, CX, CY, BY and all this stuff. If you look at the the the little red diagram this point is X1 Y1. And you know, it's in the diagram what the points are. So, the first function call pretty much says apply the rule to this segment. The second function call starts from A, which is this point here. Which says apply the rule to this segment. The third one starts at C, which is the top point.
嗯，好，我们来看看实际的代码。你们看到中间那四个对 create curve 的函数调用了吗？X1 Y1、AX、AY、CX、CY、BY 等等这些东西。如果你看那个红色的小示意图，这个点就是 X1 Y1。然后你知道，图里标出了这些点分别是什么。所以第一个函数调用基本上就是说：把规则应用到这一段上。第二个函数调用从 A 开始，也就是这里这个点。意思是把规则应用到这一段上。第三个从 C 开始，也就是顶点。
19:25
And says apply the rule to this segment. And and the fourth one applies rule to this. So, it's it's another beautiful recursive fractal. So, what happens um So, this is the Koch curve. If you generalize this and add a randomness to it say you know, say these points are A you know, it doesn't matter what they're called. If you move this one up and down a little bit randomly. So, like you start from this, instead of making these points exact, make them like a little bit off. And then connect the lines and make a line a triangle there.
意思是把规则应用到这一段上。第四个则把规则应用到这一段上。所以这又是一个漂亮的递归分形。那么会发生什么呢，嗯，这就是科赫曲线。如果你把它推广一下，加入一些随机性，比如说这些点是 A，你知道，叫什么名字并不重要。如果你把这个点随机地上下移动一点点。就是说，你从这个开始，不要让这些点的位置那么精确，让它们稍微偏一点。然后把线连起来，在那里做出一条线、一个三角形。
05有限面积无限周长：英国海岸线之问
20:10
And this is also, you know, a little bit off. And then if you keep doing this, adding a little bit of randomization each time, you actually get lines that look just like coastlines around you know, pieces of land. And if you generalize this into three dimensions and do this randomness, it actually generates 3D mountains, like 3D virtual 3D surfaces that look exactly like real mountains. So, it's sort of strange like these recursive structures are are definitely in nature. What does it mean for this one page on page six? The Koch snowflake has finite area but infinite Oh, yeah. Yeah, I forgot to mention that. That's a really cool thing. So, the Koch snowflake is when you start with a triangle and you apply the rule to each sides of the triangle.
这个也稍微偏一点。然后如果你一直这样做下去，每次都加入一点随机化，你实际上会得到看起来就像陆地边缘海岸线的线条。如果你把这个推广到三维并加入这种随机性，它实际上能生成三维的山脉，就像三维的虚拟三维表面，看起来跟真实的山一模一样。所以这有点奇妙，这些递归结构确实存在于自然界中。第六页上这一页说的是什么意思？科赫雪花的面积是有限的，但周长是无限的——哦，对，对，我忘了提这个。这是个非常酷的事情。科赫雪花就是你从一个三角形开始，把规则应用到三角形的每一条边上。
21:04
And you get you get the you get this curve on all these sides. So, it's been mathematically proven or you know, extrapolated that if you if you were to do this rule an infinite number of times, which you can do in math cuz it's all theoretical, uh the volume inside of this object would be finite. It's it's a definite amount. But the surface area is infinite. Oh, not surface area. The perimeter. Perimeter is infinite. That's because every time you apply the rule, you actually increase the perimeter.
然后你在所有这些边上都得到这种曲线。所以数学上已经证明了，或者说推导出来了，如果你把这个规则执行无限多次——在数学里你可以这么做，因为都是理论上的——呃，这个图形内部的体积会是有限的。它是一个确定的量。但表面积是无限的。哦，不是表面积，是周长。周长是无限的。这是因为每次你应用这个规则，实际上都会增加周长。
21:40
So, this uh has a certain length. And then once you apply the rule to it, if you do this, then this new curve, the total length is longer than this one. So, you can imagine if you do it infinitely, like it's just going to be infinitely long. So, it's it's sort of mind-boggling. And this this goes, you know, it's a If you like go near a certain number of iterations, it's going to get smaller and smaller. Yeah, it it gets smaller and smaller, definitely. But if you do it theoretically an infinite number of times, like it'll still exist. If you look at the picture, um on page six, right next to the title, the Koch snowflake, that curve there, you see it?
所以这个呃有一定的长度。然后一旦你对它应用规则，如果你这样做，那么这条新曲线的总长度就比原来这条更长。所以你可以想象，如果你无限次地做下去，它就会变得无限长。所以这挺让人费解的。而且这个，你知道，如果你做到一定的迭代次数，它会变得越来越小。是的，它确实会变得越来越小。但如果理论上你做无限多次，它仍然会存在。如果你看那张图，嗯，第六页上，就在标题旁边，科赫雪花，那里那条曲线，你看到了吗？
22:34
That's sort of what it would look like even if you did it an infinite number of times. So, if I I could have like break it maybe like cut it in half and then like spread it, it go on infinitely. Say again? If I could like maybe have like a kind of like a snowflake like that. And I like cut like it in half like I I just cut it like So, like you you just cut it in half? Yeah, not not in half but just cut like one part of it. I don't want like the segments to go from like one part to the other but just cut it like you would like cut like a string in a circle.
就算你重复无限多次，大概也就是这个样子。所以，如果我，我可以把它掰开比如从中间剪断，然后把它拉开，它就能无限延伸下去。再说一遍？如果我有一个类似那样的雪花图形，然后我把它从中间剪开我就这么剪一下——所以，你是说你把它从中间剪断？对，不是正中间，就是剪掉它的某一部分。我不是想让那些线段从一边连到另一边，而是就这么剪一下，就像你剪断一根围成圆圈的绳子那样。
23:10
I don't really understand. You can draw it on the board if you want. On the board?
我不太明白。你想的话可以到黑板上画出来。到黑板上？
23:21
I have like a circle. I just cut like this part over here and then if I even if this this is like finite area, you're saying that if I cut it like that and spread it, it can go on infinitely but that doesn't make I see. So, it's like having a finite area. I see what you mean. So, say you have this Koch curve, this shape, and it were a string and you would cut it so the string would now be loose. And if you pulled it, it would go on forever. Yeah. It would. Yeah. That's what it means to have infinite perimeter, which is why it's just so fascinating.
比如我有一个圆。我就在这个位置剪一下，然后，就算这个东西的面积是有限的，你是说如果我这样剪断然后把它拉开，它可以无限延伸下去，但这说不通——哦，我懂了。所以就是说它的面积是有限的。我明白你的意思了。假设你有这条科赫曲线，这个图形，假如它是一根绳子，你把它剪断，绳子就松开了。然后你一拉，它就会无限地延伸下去。对。确实会。对。这就是周长无限的含义，所以才这么让人着迷。
24:06
Like it's crazy. People tried to measure the coast of Britain. How long is the coast of Britain, right? Have you heard about this problem? If you look at it on a larger on a large scale, like from a satellite image of the whole country, you could just draw a line around it and say like, "Oh, yeah, it's this length. This is the how the length of the coast of Britain." But if you zoom in on it, you'll find that those big lines that you drew are actually like really wrong. Like they don't actually line up. So, if you make it more precise to this new zooming angle, this zooming, uh it gets longer.
简直太不可思议了。有人试图测量英国的海岸线。英国的海岸线到底有多长？你们听说过这个问题吗？如果你从很大的尺度上看，比如从整个国家的卫星图像上看，你可以沿着它画一条线，然后说：“哦，就是这么长，这就是英国海岸线的长度。”但如果你放大来看，就会发现你画的那些大线条其实非常不准确，根本对不上。所以，如果你按照放大后的这个尺度画得更精确，长度就会变长。
24:39
And so actually the more that you zoom in on the coast of Britain, the longer the perimeter gets. And those should be getting smaller cuz you're like just adding little little pieces. Yeah, just adding little pieces. So, say the actual um coast of Britain is like that. And but you look at it like at this huge distance away, you say like, "Oh, yeah, this is approximately that line." But if you look at it more detail and refine it, you say, "Oh, it's not actually that line. It's maybe like these lines."
所以实际上，你把英国海岸线放大得越厉害，周长就越长。可这些增量应该会越来越小才对，因为你只是在加一些小碎片。是啊，只是加一些小碎片。所以，假设英国海岸线实际长这样。但你从很远的距离看，你会说：“哦，差不多就是这条线。”可你看得更细致、更精确一些，你就会说：“哦，其实不是那条线，可能是这几条线。”
25:10
But the new lines are actually the whole thing is longer. And if you do it even more and more precisely, you just get longer and longer and longer. So, nobody's been able to really figure out how long the coast of Britain is. It's a fractal. Yeah, but shouldn't you do like Is it even possible like in this world like have like something that's infinitely precise? Like we would need a fraction. Well, not really. Cuz I mean, it's the the So, he asks like, is it possible in this world to have something that's really infinite like that?
但这些新的线加起来整体反而更长。而如果你做得越来越精确，它就会越来越长、越来越长。所以，从来没有人真正搞清楚英国的海岸线到底有多长。这是个分形。是啊，但是难道不该……在这个现实世界里，真的有可能存在无限精确的东西吗？我们大概需要一个分数。嗯，其实不太可能。因为我是说，这个——他问的是，在这个世界上有可能存在那种真正无限的东西吗？
25:44
Uh no, it's not. Cuz I mean, there's only finite space on the earth. Yeah, but even even within that, I mean, you you just say that even if it has finite area or maybe volume, it can still have like infinite perimeter. Yeah, so the Koch curve theoretically, you know, in math language, if you do it mathematically, it has infinite perimeter but finite area. But keep in mind this is a theoretical creation. It's just in the world of math. And it can't really exist in the universe. But things come pretty close to it in nature.
呃，不可能。因为地球上的空间是有限的。对，但即便在这个范围内，我是说，你刚刚说了，即使它的面积、或者体积是有限的，它仍然可以有无限的周长。是的，所以科赫曲线在理论上，用数学的语言来说，如果你从数学上去做，它有无限的周长但有限的面积。但要记住，这是一个理论上的构造。它只存在于数学的世界里。它在宇宙中并不能真正存在。但自然界里有些东西相当接近它。
06谢尔宾斯基三角形与混沌游戏
26:21
It's not actually infinite. The coastline of Britain is not actually infinite. But it's it's it really resembles this sort of shape. So, let's see. Yeah. So, any any questions about the Koch curve? It's really interesting. So, the next example is um the Sierpinski triangle, page eight. So, the Sierpinski triangle is very interesting. Well, uh You take a big triangle and you add a smaller triangle inside of it like this. So, this is the rule for the Sierpinski triangle. And uh you know, this is let's call it that or something.
它并不是真的无限。英国的海岸线并不是真的无限长。但它确实非常像这种形状。那么，我们来看看。好。关于科赫曲线还有什么问题吗？真的很有意思。那么下一个例子是谢尔宾斯基三角形，第八页。谢尔宾斯基三角形非常有意思。嗯，你取一个大三角形，然后在里面加上一个像这样的小三角形。这就是谢尔宾斯基三角形的规则。然后，嗯，我们就把这个叫做这个之类的吧。
27:22
So, this is the rule and what you get is three new triangles. And then you apply the same rule to these new triangles. So, that's recursion. When you apply a rule to something that you already applied the rule to, so you apply it again and you get these even smaller things, these smaller triangles, and it goes down infinitely if if you do it infinitely. So, imagine this. This So, this is one way of computing it, one way of doing it, one way of looking at the rule. But um what I did in the If you look at the the lecture notes, I talk about iterated function system.
这就是规则，而你得到的是三个新的三角形。然后你对这些新的三角形应用同样的规则。这就是递归——你对一个已经应用过某条规则的东西再次应用这条规则，于是你再来一次，就得到了这些更小的东西，这些更小的三角形，如果你无限做下去，它就会无限地分下去。所以想象一下。这就是计算它的一种方式，做出它的一种方式，理解这条规则的一种方式。不过呃，我在……如果你看一下讲义笔记，我在里面讲了迭代函数系统。
28:08
So, that means um Well, I'll just do it and you'll see what it means. So, let's say we start with a point. Uh say this point here. It could be any point. Um And we have three possible choices. This is called the chaos game. We have three possible choices of something to do with this point. We either bring it halfway to this point, halfway to this point, or halfway to this point. So, let's say we bring it halfway to this point. We go right here, right in the middle. And what we do in the iterated function system, we do this over and over and over again, picking randomly which one of the three points we go halfway towards.
所以，那意思是呃……好吧，我直接做一遍你就明白了。假设我们从一个点开始。呃，比如这里这个点。它可以是任意一个点。呃，然后我们有三种可能的选择。这个叫做混沌游戏。对这个点，我们有三种可能的操作选择。我们要么把它移到通往这个点的一半处，通往这个点的一半处，或者通往这个点的一半处。那么，假设我们把它移到通往这个点的一半处。我们就走到这里，正中间。而在迭代函数系统里我们要做的，就是把这个过程一遍又一遍地重复，随机挑选这三个点中的哪一个作为我们要走一半路程的目标。
28:48
So, let's say we go to this one next. We go here, halfway. Then we go halfway to this one. Halfway to this one again. Halfway to this one again. And then halfway to this one. Um then halfway to this one. Halfway to this one. You know, and halfway to this one, halfway to this one, halfway to this one. So, we just plot these points. And um the program that I wrote, which is in the handout, does this. It executes this. It just keeps going. It keeps plotting the points. And eventually what you get is the Sierpinski triangle.
那么，假设我们接下来走向这个点。我们走到这里，一半处。然后我们走向这个点的一半处。再走向这个点的一半处。再一次走向这个点的一半处。然后走向这个点的一半处。呃，然后走向这个点的一半处。走向这个点的一半处。你知道的，再走向这个点的一半处，这个点的一半处，这个点的一半处。然后我们就把这些点画出来。呃，我写的那个程序，就在讲义里，做的就是这件事。它执行的就是这个过程。它就一直做下去。它不停地画出这些点。最终你得到的就是谢尔宾斯基三角形（Sierpinski triangle）。
29:26
It's crazy. So, page eight is the picture of this is on page eight, right? Yeah. So, when you do it randomly, it doesn't matter which one you choose. No matter what you choose, whenever you do it, it's always going to look the same. So, So, if I like started the program again, but now this time it since it's random, it's going to be like Yeah. Exactly. So, he's getting at So, you run the program again, it's going to choose differently. Maybe it'll choose instead of going to this one first, it'll go to this one first. Say it does it 10 times or 100 times to this one.
太不可思议了。所以第八页是这个的图，图在第八页，对吧？对。所以，当你随机地做这件事时，你选哪一个都无所谓。不管你怎么选，不管你什么时候做，结果看起来总是一样的。所以，所以如果我比如说重新启动这个程序，但这次因为它是随机的，它就会像是……对。没错。所以他想问的是……你重新运行这个程序，它会做出不同的选择。也许它不会先走向这个点，而是先走向那个点。比如说它连续 10 次或 100 次都走向这个点。
30:08
Um but it the program chooses randomly which one to go to. Going to go to this one and it just chooses randomly. So, he asked, even though it's random, will it still generate the same picture? And the answer is yes, it will. Uh it's crazy. It's just just fascinating. And we'll understand this better after we do the next example, which is making a fern, a fractal fern. Which is really cool. So, let's just look at the code quickly. Um and think about this, is the code for the Sierpinski triangle recursive?
呃，但程序是随机选择走向哪一个的。要走向这个点，它就是随机选的。所以他问，即使它是随机的，它还是会生成同样的图像吗？答案是：是的，会的。呃，太疯狂了。真的非常迷人。等我们做完下一个例子之后，你们会更好地理解这一点——下一个例子是画一棵蕨，一棵分形蕨。那个真的很酷。那我们快速看一下代码。呃，然后想一想，画谢尔宾斯基三角形的这段代码是递归的吗？
30:47
So, what it does is see def draw Sierpinski, that's the thing that draws the triangle. A def A, B, and C are these three points. So, this is like A, B, and C. Def points equals a list of A, B, and C. Current point is just a you know, say start at point A. While this statement while true means execute this code repeatedly. Just keep doing it an infinite number of times until until you stop the program. So, it says def next point equals pick from points. And pick from is a function defined above, which pretty much picks at random out of the list that you give it.
它做的事情是这样的，看 def draw Sierpinski，这就是画三角形的那个东西。def 里的 A、B、C 就是这三个点。所以这就相当于 A、B 和 C。def points 等于一个由 A、B、C 组成的列表。current point 就是一个……你懂的，比如说从点 A 开始。while 这个语句，while true 意思是重复执行这段代码。就一直做下去，做无限多次，直到你把程序停掉。所以它写着 def next point 等于 pick from points。而 pick from 是上面定义的一个函数，它基本上就是从你给它的列表里随机挑一个出来。
31:39
So, that pick from is the thing that picks randomly which one of these to go to. So, it says okay, next point pick from points. So, that gives you the point. And then current point X equals current point X plus next point X divided by two. So, what you're doing is averaging the X coordinates of the current point and the point that you're going to go to next. And if you do that for X and Y, what you do is go that's going halfway between the current point and the next point. That's what that does. Then image.fill pixel that point. So, that that's what plots it on the screen.
所以那个 pick from 就是随机决定要走向这几个点中哪一个的东西。所以它说，好，next point 等于 pick from points。这样你就得到了那个点。然后 current point 的 X 等于 current point 的 X 加上 next point 的 X 再除以 2。所以你做的事情就是把当前点和你接下来要走向的那个点的 X 坐标取平均值。如果你对 X 和 Y 都这么做，你所做的就是走到当前点和下一个点的正中间。那句代码做的就是这个。然后 image.fill pixel 那个点。所以那就是把它画到屏幕上的部分。
07递归为何必须触底：学生问答
32:16
And the the picture here is actually was actually generated by this very program. Um So, it just keeps going, keeps plotting it. So, here's the question, is this recursive? Is this thing actually recursive? Cuz we said a recursive function is a function that calls itself. Um let's hold off on that answer until after we do the next one. Any questions so far? So, the next thing we're going to do is the fern. Yeah. So, recursion is generally recursion is something which is defined in terms of itself.
而且这里这幅图实际上就是由这个程序生成的。呃，所以它就一直运行，一直画。那么问题来了，这是递归的吗？这个东西到底是不是递归的？因为我们说过，递归函数是一个调用自身的函数。呃，这个答案我们先放一放，等做完下一个例子再说。到目前为止有什么问题吗？那么我们接下来要做的就是那棵蕨。请讲。所以，递归一般来说是用它自身来定义的东西。
32:59
Something that loops back on itself.
一种回到自身的循环。
33:06
Again? If you apply which one? The recursive rule? It'll become the same thing that it started with? Uh no, not necessarily because each time it applies the rule, there's a slight change. With this factorial, it's not just saying n factorial equals n factorial, it's saying n factorial equals n minus 1 factorial. The factorial part is recursive, but it doesn't loop back on itself exactly. There's some change. And with recursive functions at least, um so, the function is defined, it calls itself. Maybe this I don't know if this really answers your question, but say if we didn't have these parts, if the function just was this, if def Fibonacci return Fibonacci of n minus 1 n minus 2, what would happen is it would call itself and just keep going infinitely.
再说一遍？如果你应用哪一个？那个递归规则？它会变成和它开始时一样的东西吗？呃，不，不一定，因为它每次应用规则时，都会有一点小小的变化。以这个阶乘为例，它并不是说 n 的阶乘等于 n 的阶乘，而是说 n 的阶乘等于 n 减 1 的阶乘。阶乘那部分是递归的，但它并不是原封不动地绕回自己。中间是有变化的。至少对递归函数来说，嗯，就是说，函数定义好之后，它会调用自己。也许这个……我不知道这是不是真的回答了你的问题，不过假设我们没有这几部分，假设这个函数就只有这一句，如果 defFibonacci 返回 Fibonacci(n-1) 加 Fibonacci(n-2)，那结果就是它会不断调用自己，一直无限进行下去。
34:11
Which is a problem, so all recursive functions in order to do anything have to bottom out at some point. They have to stop, and that's what this is. Only do this if x if n is greater than 1. If if n is less than or equal to 1, return. So, this stops it. So, I mean d- does that answer your question? I don't know. You can ask it again if you want.
这就有问题了，所以所有递归函数要想真正做点什么，都必须在某个点上触底。它们必须停下来，而这就是这部分的作用。只有当 x……当 n 大于 1 时才这么做。如果 n 小于或等于 1，就返回。所以，这就让它停下来了。所以，我是说，这有没有回答你的问题？我也不确定。如果你想的话，可以再问一次。
34:42
It is. Yeah. Yeah.
是的。嗯。嗯。
34:51
It only functions, computer functions that are that are recursive need to bottom out. There are other kinds of recursion. Um well, they they do. Like natural recursions don't bottom out. Well, they do have to bottom out eventually. Like take for example a tree in nature. It branches and branches and branches, but eventually it just gets to a leaf. And it stops branching. There's some sort of program that's that's executing inside this tree that's recursive. And there's a certain signal that this program gets when the branch gets to a certain size, I think or something, that signals it to generate a leaf. So, I mean those kind of recursive processes do bottom out.
它只是……函数，计算机里那些递归的函数需要触底。还有别的种类的递归。呃，其实它们也是的。比如自然界中的递归就不会触底。其实它们最终也得触底。比如就拿自然界里的一棵树来说。它不断分叉、分叉、分叉，但最终总会长到一片叶子。然后就不再分叉了。这棵树内部有某种正在执行的程序，而它是递归的。而且当树枝长到某个尺寸的时候，这个程序会收到某种信号，我想大概是这样，这个信号让它去长出一片叶子。所以，我是说，那类递归过程确实是会触底的。
35:35
But this one is actually recursive. We'll see why in a minute, but it doesn't bottom out because it just keeps going forever.
但这一个其实是递归的。过一会儿我们就会看到原因，但它不会触底，因为它就这样永远进行下去。
36:08
Yeah, exactly. Exactly. Yeah, that was that was very well put. So, what he's basically said was if you want to get any real manifestation of recursion, it has to bottom out in order to return you the result. But yeah, you can imagine theoretical worlds where it doesn't bottom out. Go on and on forever. Actually, Douglas Hofstadter in the dialogue before this chapter does that. A genie has to ask a meta genie has to ask a meta genie. Did Did anybody read that? Yeah, I but it it is the thing with time it goes in it gets smaller and smaller and Yeah, the time is smaller and smaller.
对，没错。完全正确。嗯，说得非常好。他刚才基本上说的是，如果你想得到递归的任何真实体现，它就必须触底，才能把结果返回给你。不过没错，你可以设想一些理论上的世界，在那里它不触底。一直不停地进行下去。其实道格拉斯·侯世达在这一章前面的对话里就写了这个。一个精灵要去问一个元精灵，元精灵又要去问元元精灵。有人读过那段吗？嗯，我……不过那个和时间有关的地方，它会越来越小，越来越小。对，时间越来越小。
08分形蕨：迭代函数系统与坐标变换
36:43
So, like eventually you know, you just repeat an infinite number of intensely small Yeah. Yeah, isn't that crazy? Yeah, it's really something to think about. Yeah. But keep it's like theoretical, but but it is very interesting to think about. So, we'll see how this is recursive after we do the fern. So, the fractal fern is next, page nine. Um Yeah, this is really really cool. Um
所以，最后你知道的，你就在无限多个极短的时间里重复……对。对，这是不是很疯狂？是啊，真的很值得琢磨。对。不过要记住，这算是理论上的，但确实非常有意思，值得去想一想。那么，等我们做完蕨类之后，就会看到这个是怎么递归的。所以接下来是分形蕨，第九页。嗯，这个真的非常非常酷。嗯
37:26
So, the fractal fern uh it looks beautiful, doesn't it? So, we have this this triangle. Um this this isn't the picture in the handout. There's an outside triangle that's black. And then there's an inside triangle that's blue and some other triangles that that are the leaves. So, first of all, I want to talk about this notion of a coordinate transformation. You have Say we had a a coordinate transformation between this rectangle and this rectangle. What would happen it like it's it's a function on a point, a two-dimensional point.
那么这个分形蕨，呃，它看着很漂亮，是不是？所以我们有这个这个三角形。嗯，这个……这不是讲义里的那张图。外面有一个三角形是黑色的。然后里面有一个三角形是蓝色的，还有另外一些三角形，就是那些叶子。那么首先，我想讲一讲坐标变换这个概念。你有……假设我们在这个矩形和这个矩形之间有一个坐标变换。会发生什么呢，它就像是作用在一个点上的函数，一个二维的点。
38:09
So, say you had the point right here, this point. You apply this transformation to the point, and what you get is this point here. Um so, you have this point here and you apply the transformation to that point, you'll get this point here. It's just like a little copy of this. Okay? So, this is a function, this is the function part of iterated function systems. Iteration is the fact that you just keep doing it. And a system is the fact that there's more than one of them. It's like a bunch. In this case, it's three.
那么，假设你有这里这个点，这个点。你把这个变换应用到这个点上，得到的就是这里这个点。嗯，所以你有这里这个点，你把变换应用到那个点上，就会得到这里这个点。它就相当于这个的一个小副本。好吗？所以，这是一个函数，这就是迭代函数系统里的函数那部分。迭代指的就是你不停地重复做这件事。而系统指的是这样的函数不止一个。是一堆。在这个例子里是三个。
38:50
Um I'll talk about it in a minute. So, in and with the fractal fern, what we have is uh a rectangle like this.
嗯，我等一下会讲到。那么，在分形蕨里，我们有的是，呃，像这样一个矩形。
39:14
So, this the fractal fern is an iterated function system that has four possible functions. This one has three. Each one of those points is one is a function. You know, going halfway to one of those points is a function. But in the fern one, there are four functions. This is one of them. Um and each function is a coordinate transformation. This function is a coordinate transformation from this outer one, this outer rectangle to this inner rectangle. So, if we had this point in this rectangle and we applied this transformation, we would get this point here.
所以这个……分形蕨是一个迭代函数系统，它有四个可能的函数。这一个有三个。那些点里的每一个都是一个函数。你知道，走到那些点中某一个的一半路程，这就是一个函数。但在蕨类那个例子里，有四个函数。这是其中之一。嗯，每个函数都是一次坐标变换。这个函数是从外面这个、这个外层矩形到里面这个矩形的坐标变换。所以，如果我们在这个矩形里取这个点，然后应用这个变换，我们就会得到这里的这个点。
39:53
Um So, say say we have the middle point of this outer rectangle. And we apply this transformation once. We would get the middle point of this inner rectangle, which is about right here. But here, what we do is we say, "Okay, now this new point is actually in the outer rectangle." And we'll apply the transformation again on that. So, this this point in the outer rectangle maps to about this point in the smaller rectangle. And then you say, "Okay, this point is now a point in this one." And you apply it again.
嗯，所以，比如说我们取这个外层矩形的中点。然后我们应用一次这个变换。我们会得到这个内层矩形的中点，大概就在这里。但在这里，我们要做的是说："好，现在这个新的点其实是在外层矩形里。"然后我们再对它应用一次这个变换。那个点。所以，外层矩形里的这个点会映射到较小矩形里大概这个点。然后你说："好，这个点现在是这个矩形里的一个点。"然后你再应用一次。
40:39
And you get this point here and this point here, this point here. And like all these little points. And eventually, they just get smaller and smaller. Because the corner points of these two rectangles are the same point. I think. Probably, yeah. They're the same point. So, let's look at another one. Um Let's see.
于是你得到这里这个点、这里这个点、还有这里这个点。以及所有这些小点。最后，它们会变得越来越小。因为这两个矩形的角点是同一个点。我想是吧。大概是的，是的。它们是同一个点。那我们再来看另一个。嗯，我看看。
41:16
So, this is the um the thing that's going to map to. It It's It's so It's a line. But think of it as a a rectangle. It's It's a coordinate transformation. So, we go from any point in this outer rectangle to a point on here. So, say if we have this point here in the outer rectangle, it's going to go to the top point of this line. If we have this point here, it's going to go to the bottom point of this line. If we have the center point, it'll go to the center of this line. So, let's imagine an iterated function system with only these two functions.
所以，这就是那个要映射过去的东西。它是……它是……所以它是一条线。但你可以把它想成一个矩形。它是……它是一个坐标变换。所以我们从这个外层矩形里的任意一点，映射到这上面的一个点。所以，比如我们在外层矩形里取这里这个点，它会映射到这条线的最上面那个点。如果我们取这里这个点，它会映射到这条线的最下面那个点。如果我们取中心点，它会映射到这条线的中心。那么，我们来想象一个只有这两个函数的迭代函数系统。
41:55
What's going to happen is and let's say each one is chosen Well, let's say each one is chosen about half the time randomly. Picks between each one. Or no, let's say that it applies this mapping about 90% of the time. So, say we start with this point here, it'll map to this point here, this point here. And it'll just go up and up into here as long as this transformation is being applied. But say it does that like 100 times and then one time it goes down to here. So, say it's all the way up here and we map to this one, it's going to start here.
接下来会发生的是……我们假设每个函数被选中的概率……嗯，我们假设每个函数大约有一半的概率被随机选中。在两者之间随机挑选。不对，我们假设它大约85%……大约90%的时候应用这个映射。那么，假设我们从这里这个点开始，它会映射到这里这个点，再到这里这个点。只要一直在应用这个变换，它就会不断往上、往上，一直到这里。但假设它这样做了大概100次，然后有一次它跑到了这里下面。所以，假设它一路上到了这里，然后我们映射到这一个，它就会从这里开始。
42:38
And it's going to map here, here, here. It's going to go up. And say we stop at this point, the computer decides to map to to here. It's about, you know, 3/4 up. It's going to go to 3/4 up here. So, because it's random, if you do this just forever, it's going to eventually fill in pretty much every point on this line. Which is very interesting to think about. Any questions so far? So, let's have this this rectangle. All four of the transformations are from the outer rectangle, this big one, to one of the ones inside, one of the smaller ones inside.
然后它会映射到这里、这里、这里。它会往上走。假设我们在这一点停下，计算机决定映射到这里。它大概在，你知道，四分之三的位置。那它就会映射到这里四分之三的位置。所以，因为这是随机的，如果你一直这样做下去，最终它几乎会填满这条线上的每一个点。这想起来非常有意思。到目前为止有什么问题吗？那么，我们来看这个矩形。这四个变换都是从外层矩形、就是这个大的，映射到里面某一个、里面某个较小的矩形。
43:24
So, say we have this point up here and we apply this transformation to this one. It's going to go to this point here. Make sense? And if we have this one, it's going to go to this point here. So, the transformation is pretty much going like this. So, say our IFS, iterated function system, has these three. Say we go about halfway up here and we choose to to apply this mapping. It's going to go about here, the middle of this one. And then we apply this mapping like a bunch of times. Just keep going up and up and up.
所以，假设我们在上面这里有个点，我们对它应用这个变换，映射到这一个。它会跑到这里这个点。说得通吗？如果我们取这一个，它会跑到这里这个点。所以，这个变换大概是这样走的。那么，假设我们的IFS，也就是迭代函数系统，有这三个函数。假设我们走到这里大概一半高的位置，然后我们选择应用这个映射。它会跑到大概这里，也就是这个的中间。这一个的中间。然后我们把这个映射应用很多次。就一直往上、往上、往上。
44:03
We apply this mapping again. But it's so closer to the top this time, so it's going to be out here, closer to this the top of this rectangle. And then we apply it again and again and again. And maybe it only goes up one. So, it'll be down here. So, eventually, it's going to fill in this rectangle with this pattern. It's going to look like this. Okay? And this, since that's, you know, every point in here is probably going to get applied to this mapping a bunch of times. So, what we're going to get is this fern structure.
我们再应用一次这个映射。但这次它离顶部更近了，所以它会跑到这外面来，更靠近这个矩形的顶部。然后我们再一次又一次地应用它。也许它只往上走了一格。那它就会在这下面。所以，最终，它会用这个图案填满这个矩形。看起来会是这样。好吗？而且这个，因为，你知道，这里面的每一个点大概都会被这个映射作用很多次。所以我们得到的就是这个蕨类结构。
44:52
Okay. Isn't that really cool? You're saying that all of the points in those smaller in that little small triangle uh the points that you have in there applied to like the biggest one to like different parts of the biggest one or do you like Are you Are you talking about the Sierpinski triangle or the fern? The fern. Okay. Like you have like a bunch of points in that little like Do those Do all those like little points that correspond like one of the either one either like parts of the fern Yeah. It's like they're repeated, but only smaller and each one has the same amount of points that they have. Yeah, exactly.
好。是不是特别酷？你是说，那些小的……那个小三角形里的所有点，呃，你在里面取的那些点，被映射到最大的那个上面，映射到最大那个的不同部分？还是说你……你是在说谢尔宾斯基三角形还是蕨类？蕨类。好的。就是说你在那个小的里面有一堆点……那些……所有那些小点是不是都对应……对应蕨类的某一部分？是的。就好像它们是重复的，只是更小，而且每一个都有相同数量的点。是的，没错。
45:32
I mean, if you like get smaller and smaller, how can you get into the same amount of stuff? Right, you can't actually. And this is Okay, I'll go through an an example. Say say we have, instead of just applying it to one point, we apply it to a bunch of points. Say all the points on this line or almost all the points on there. Say we apply this this mapping a bunch of times till we get this one, this one, this one, this one, this one. And say we apply this mapping to all of these points. It's going to map to here.
我是说，如果你越变越小，怎么可能装进同样多的东西呢？对，实际上不能。这就是……好，我举个例子。假���我们不只是把它应用到一个点上，而是应用到一堆点上。比如这条线上的所有点，或者说几乎所有的点。假设我们把这个映射应用很多次，直到我们得到这一个、这一个、这一个、这一个、这一个。然后假设我们把这个映射应用到所有这些点上。它会映射到这里。
46:13
And then we do that again and again and again. And say and then what we have, say all those points eventually are going to get mapped to this one. So, you have a whole little copy of this thing in here. So, you have these little um branches. And then that is going to be mapped up here. And you have the branches, branches, branches. And then since you have the smaller branches here, you have two levels down. And this whole thing gets mapped back onto here, including the new branches. And it gets filled in as it goes on.
然后我们再一次又一次地这样做。然后假设……我们得到的是，所有那些点最终都会被映射到这一个上。所以你在这里面就有了这整个东西的一个小副本。于是你就有了这些小的，嗯，分枝。然后那个又会被映射到上面这里。你就有了分枝、分枝、分枝。然后因为你这里有更小的分枝，你就往下多了两层。而这整个东西又被映射回这里，包括那些新的分枝。随着过程继续，它就被填满了。
46:54
But it doesn't just keep going up to here and just like say we were to apply this mapping 100% of the time. It would just go up here and go nowhere else. But say we we apply this mapping like 7% of the time, it'll go up different lengths and then it'll map back down there and go up, map back down. And then if we add this transformation going from this one to this one, we have this. And it's recursive. The reason why it's recursive is because the mappings map onto themselves eventually. If we look at the code, it's it's really similar to the Sierpinski triangle code.
但它不会只是一直往上到这里，就好像……假设我们100%的时候都应用这个映射。那它就会一直往上走到这里，哪儿也不去了。但假设我们大概7%的时候应用这个映射，它就会往上走不同的长度，然后再映射回下面那里，再往上，再映射回下面。然后如果我们再加上从这一个到这一个的这个变换，我们就得到了这个。而且它是递归的。它之所以是递归的，是因为这些映射最终会映射到它们自己身上。如果我们看代码，它跟谢尔宾斯基三角形的代码非常相似。
47:41
The code itself is not recursive, but the mappings are. And that's what makes this whole thing recursive. Um So, yeah, let's just look at the code a little bit. Uh class fern. So, draw fern. While true, so that means execute this. Just keep doing it over and over and over. Pick from these list of transformations. So, the first one says maps to the stem. That means it goes from here to here, to the stem. The second one maps to the left branch, meaning it goes from here to this one. The third one maps to the right branch, it goes down here.
代码本身不是递归的，但映射是递归的。这才是让整个东西变得递归的原因。嗯，那么，好，我们稍微看一下代码。呃，class fern（蕨类类）。那么，draw fern（画蕨类）。while true，也就是说执行这个。就一遍又一遍地一直做下去。从这个变换列表里挑一个。所以，第一个写的是映射到茎。意思是它从这里到这里，到茎。第二个映射到左边的分枝，意思是它从这里到这一个。第三个映射到右边的分枝，它跑到下面这里。
48:25
And the fourth one maps from here to here. It just goes up like that. And following that, it says pick from a list of functions and then a list of probabilities. It says .01, .07, .07, .85. So, these are the probabilities at which these mapping functions are going to be chosen. If you choose them all equally, then the chances are very low that this mapping is going to occur more than like five times or something. So, it just go up here and get mapped. So, it'd be a very sparse fractal. Uh it would be most of the points would be like down here.
第四个是从这里映射到这里。它就是像这样往上走。接下来它说，从一个函数列表和一个概率列表里挑选。上面写着 .01、.07、.07、.85。所以，这些就是这些映射函数被选中的概率。如果你让它们的概率都相等，那么这个映射连续出现超过大概五次的概率就非常低。所以，它就会往上走一点然后被映射走。这样得到的分形就会非常稀疏。呃，大部分的点都会在下面这里。
09代码不递归但映射递归：跳出系统
49:06
It just didn't look very good. I tried it. I wish I could like code it and show you. Um So, the .01 means that the mapping to the stem happens 1% of the time. The mapping to each of the branches happens 7% of the time. And the mapping up and spiraling happens 85% of time. So, I'm going to take a break now for 10 minutes. Do you have any questions? So, I guess we'll start up again. Before we leave these iterated function systems, I want to point out how the Sierpinski triangle is pretty much the same thing as the ferns in terms of mappings.
看起来就很不好看。我试过。真希望我能现场写代码演示给你们看。嗯，所以 .01 表示映射到茎的情况有1%的概率发生。映射到每个分枝的概率是7%。而向上盘旋的那个映射有85%的概率。那么，我现在要休息10分钟。你们有什么问题吗？好，我想我们再开始吧。在我们离开迭代函数系统这个话题之前，我想指出，从映射的角度看，谢尔宾斯基三角形跟蕨类基本上是同一回事。
50:05
With the Sierpinski triangle, we have these three mappings. Um one of them maps from this triangle to this triangle here. One of the maps from the big triangle to this triangle. And this the other one maps from this triangle to this triangle. And each one of them are applied with equal probability. Um so, if you think about it, going halfway from any of these points to one of the other points is essentially mapping it down. So, say you have this one this line. You apply the function to all these points.
对于谢尔宾斯基三角形，我们有这三个映射。嗯，其中一个是从这个三角形映射到这里这个三角形。其中一个映射是从大三角形映射到这个三角形，另一个是从这个三角形映射到那个三角形。而且每一个映射被应用的概率都相等。嗯，所以，如果你想一想，从这些点中的任意一个走到另一个点的一半距离，本质上就是把它映射下去。比如说，你有这条线。你对所有这些点应用这个函数。
50:46
What it does is maps it down to that triangle. So, these you could see these this these triangles map onto themselves recursively. And that's why it actually it there is a recursion going on here, but it's not in the code itself. The code itself is just repetitive, but what it's repeating is these recursive mappings onto themselves. Yeah. So, there's always more than one way to like represent an algorithm? There's always more than one way to represent an algorithm. Uh Yeah, it's really fascinating.
它所做的就是把它映射到那个三角形上。所以，你可以看到这些三角形是递归地映射到它们自身的。这就是为什么这里其实确实有递归在发生，但递归不在代码本身里。代码本身只是重复性的，但它重复的正是这些映射到自身的递归映射。是啊。所以，表示一个算法总是有不止一种方式？表示一个算法总是有不止一种方式。呃，是的，这真的很迷人。
51:23
Especially with these fractals and things, it seems like there's always another way to do it, to achieve the same result. And that's one thing especially Sierpinski's triangles are really amazing. So, what if in the new code you don't have like a In my what? In in in when you like do the code, you don't have like some maybe you don't have a recursive function. So, how can you like figure out like without running the code that that your output is so kind of being recursive? Ah, so how can you figure out if the output is going to be recursive without running the code?
尤其是在这些分形之类的东西上，似乎总有另一种做法能达到同样的结果。而这一点尤其是谢尔宾斯基三角形真的很神奇。那么，如果在新代码里你没有那种——在我的什么？在你写代码的时候，你可能没有递归函数。那么，你怎么能在不运行代码的情况下，判断出你的输出是某种递归的呢？啊，所以，怎么才能在不运行代码的情况下判断输出会是递归的？
51:57
You would now you have the code, but it has no recursive function. Right. Yeah, you have the code no recursive function. If you can't run it, how can you find out that the output is going to be recursive without actually running it? So, he said uh since the code itself is not recursive, how do you know that the output is going to be recursive? Even if you don't have any recursive function. Even without any recursive functions. Right. I mean, the thing is when you write the code, if you realize that what the code is doing is mapping these these two-dimensional mappings you can sort of think in your head, okay.
现在你有了代码，但它里面没有递归函数。对。是的，你有代码，没有递归函数。如果你不能运行它，你怎么能在不实际运行的情况下发现输出会是递归的？所以，他说，呃，既然代码本身不是递归的，你怎么知道输出会是递归的？即使你没有任何递归函数。即使没有任何递归函数。对。我的意思是，问题在于，当你写代码时，如果你意识到代码在做的事情是映射这些这些二维映射，你可以在脑子里大致想象，好的。
52:38
These mappings are going to be applied with equal probability. Oops. So, just by mentally extrapolating in your head, so you're sort of stepping out of the system. You're saying, okay, what's the thing actually doing? But are you going to like do that? I mean, can you can't you just like do while you're like in the system? While you're in the system? Well, being in the system in this case is actually running the code and like being a computer program running it. Stepping out of the system, but what I mean by that is like taking a higher level view of what's going on.
这些映射将以相等的概率被应用。哎呀。所以，只要在脑子里做心理外推，你就相当于跳出了这个系统。你在说，好的，这东西实际上在做什么？但你会那样做吗？我是说，你就不能在你身处系统之内的时候做吗？在系统之内的时候？嗯，在这个情况下身处系统之内其实就是运行代码，就像是一个正在运行它的计算机程序。跳出系统，我的意思是对正在发生的事情采取一个更高层次的视角。
53:15
So, when you abstract from all of these like different what is doing the same thing, you get like this higher level which actually does your recursion. Yeah, exactly. Exactly. Yes, that's it. So, he said, when you abstract away from all the details of what's going on with the actual the functions you you begin to perceive this higher level thing which is itself recursion. Yeah, and it has recursion in it. So, if you if you abstract your thought process significantly enough you'll be able to logically tell that it's going to create this recursive shape.
所以，当你从所有这些不同的、在做同样事情的东西中抽象出来，你就得到了这个更高的层次，而它实际上做的就是你的递归。是的，正是如此。完全正确。对，就是这样。所以，他说，当你从实际函数中正在发生的所有细节里抽象出来，你就开始感知到这个更高层次的东西，而它本身就是递归。是的，而且它里面有递归。所以，如果你把你的思维过程抽象到足够高的程度，你就能在逻辑上判断出它会生成这个递归的形状。
53:56
Yeah. But there's like no like simple algorithm or like any program you have like see if it's like recursive or not. Yeah, so you mean like a test? Like Yeah, like test. No, you have to think about it. That's what humans can do. Like there's no strict test that could be applied to some computer program that would tell you whether or not it's going to create a recursive result. Cuz in this case, there's no recursive function. So, the computer can't know like, okay, hm well, this Can I abstract into Only humans can do that. Yeah, so far.
是的。但是好像没有什么简单的算法或者程序，能让你看出它是不是递归的。是的，所以你是说像一种测试？比如是啊，像测试。不，你必须自己去思考。这是人类才能做的事。就是说，没有一个严格的测试可以应用到某个计算机程序上，来告诉你它会不会产生一个递归的结果。因为在这种情况下，没有递归函数。所以计算机没法知道，好吧，嗯，这个……我能不能抽象成只有人类能做到这一点。是的，目前为止是这样。
54:29
And it's not coded up as a a system of mappings. It's just these simple functions. I don't know. So, yeah. So, it's really cool. So, yeah, if you just think about mapping mapping mapping and you map it over here, all the stuff that was in here that goes infinitely down is now like in in like this little sub section of this little triangle. And you just yeah. It's a recursive structure. So, let's go on to the next example, which is very interesting, the Mandelbrot set. Um First, now that we have this up and running, I just want to run the the the programs that are in the handout to to give you a sense of what's going on.
而且它并没有被编写成一个映射系统。它只是这些简单的函数。我不知道。所以，是的。所以，这真的很酷。所以，是的，如果你就这样想着映射、映射、映射，然后你把它映射到这边，原本在这里面无限延伸下去的所有东西，现在就像是在这个小三角形的这一小块子区域里了。然后你就……是的。这是一个递归结构。那么，我们进入下一个例子，非常有意思，曼德博集合。嗯，首先，既然我们现在把这个跑起来了，我想运行一下讲义里的那些程序，让大家感受一下是怎么回事。
55:17
So, the recursive transition network. Let's run it. See what happens. It's going to generate 100 sentences. Cuz if you look at the code uh there's a print statement that goes 100 times. Uh yeah, page five. It says 0 to 100.each print line call the function fancy noun. So, this is just fancy notation in the Groovy programming language to to Oh, crap. It's not working. Oh, well. I'll just try to get this to work as I'm talking. I can't do the examples. So, um Yeah, I've been having problems with this stay all day.
那么，递归转移网络。我们来运行一下。看看会发生什么。它会生成 100 个句子。因为如果你看代码，呃，那里有一个打印语句执行 100 次。呃，是的，第五页。上面写着 0 到 100，each，print line，调用函数 fancy noun。所以，这只是 Groovy 编程语言里的花哨写法，用来呃，糟糕。它没跑起来。唉，算了。我一边讲一边试着把它弄好。我做不了这些例子。所以，嗯是啊，我一整天都在被这东西困扰。
10曼德博集合：复平面与逃逸迭代
56:07
So, the next example and the last example is the Mandelbrot set. Um You guys probably have heard about the Mandelbrot set. It's very famous, probably one of the most famous fractals of all. Um It's called Mandelbrot because this guy Mandelbrot uh really loved fractals and tried to communicate the the notion of fractals to the world and this is really a great fractal. So, it it'll get a little bit mathy, but that's okay. Um so, we'll have it's in the complex plane. So, that means that we have this plane where these are the real numbers and these are the imaginary numbers. I think this is where it goes.
那么，下一个例子，也是最后一个例子，是曼德博集合。嗯，你们大概都听说过曼德博集合。它非常有名，可能是所有分形里最有名的之一。嗯，它叫曼德博是因为曼德博这个人呃真的很喜欢分形，并且试图把分形的概念传达给全世界，而这确实是一个很棒的分形。所以，接下来会有一点数学味，但没关系。嗯，所以，我们会在复平面上讨论。也就是说我们有这样一个平面，这边是实数，这边是虚数。我想是这么放的。
56:55
Um So, the the Mandelbrot set is defined by the function Z = Z ^ 2 + C. Um And when you square a complex number well, first of all, first of all, a complex number is a point in this plane. So, say this point is you know, this is B, say, and this is A. This point is represented by um A + B I. And I is the square root of -1, which is not really possible. That's why it's called imaginary. So, um if you multiply two complex numbers together um it's not really that simple. You have to do like the actual multiplication out. When you get is A AC + you know, I don't know if I should do it all out.
嗯，所以，曼德博集合由函数 Z = Z² + C 定义。嗯，当你对一个复数取平方时，呃，首先，首先，一个复数就是这个平面上的一个点。比如说，这个点，你知道，这是 B，比如说，这是 A。这个点用，嗯，A + Bi 表示。而 i 是 -1 的平方根，这实际上是不可能的。所以它才被叫做虚数。所以，嗯，如果你把两个复数相乘，嗯，其实并没有那么简单。你得把乘法实际展开算出来。你会得到 AC + 之类的，我不知道该不该全部算出来。
58:16
Uh it could it'll take a little bit of time. But you get this sort of a mapping function essentially that's not really linear. It's not really that predictable what it's going to do. So, you have this this point here. And Okay, so the way the algorithm works, you take a point on the complex plane. That that gets C gets the value of that point. And then Z starts off at zero. Just Just not Just zero zero. And you apply this function a bunch of times. So, say we apply this function once. Uh Z = Z ^ 2 + C. So, 0 ^ 2 is nothing + C. So, the first iteration, Z gets the value C. So, Z is going to be there. Then you apply the function again.
呃，这可能会花一点时间。但你会得到这样一种映射函数，本质上它不是线性的。它做出来的结果并不那么容易预测。所以，你在这里有这个点。那么，好的，算法是这样工作的：你在复平面上取一个点。那个点的值就赋给 C。然后 Z 从零开始。就只是，就只是零，零。然后你把这个函数应用很多次。比如说我们应用一次这个函数。呃，Z = Z² + C。所以，0² 是零，加上 C。所以第一次迭代，Z 得到值 C。所以 Z 会在那里。然后你再应用一次函数。
59:09
With with and this Z is now the new Z that that we just got. So, Z = Z ^ 2 + C. So, Z ^ you apply the squaring function. And you add C. You add the real and imaginary components of C. So, it just maps this point to some other point over here, say. Um and then you you then you apply this again and again and again and again. So, apply it here. Here here. So, I don't know if I'm going too fast, but like we get this point after applying the function to this. So, now this is the new Z. And then this the new Z loops back around.
用的这个 Z 就是我们刚刚得到的新的 Z。所以，Z = Z² + C。所以，Z 的平方——你应用平方函数。然后你加上 C。你加上 C 的实部和虚部。所以，它就把这个点映射到别的某个点，比如说这边。嗯，然后你再一遍又一遍地应用这个。所以，在这里应用。这里，这里。所以，我不知道我讲得是不是太快了，不过，对这个点应用函数之后我们得到了这个点。所以现在这就是新的 Z。然后这个新的 Z 又循环回去。
59:53
And so, we apply it now Z squared plus C. C is always going to be the initial point. But Z will be changing. And it maps to here, for example. And now the new point is Z. And you do Z squared plus C again. And that maps over here. So, uh I wrote a little applet that demonstrates the this mapping and what it actually looks like, yeah. And the C can be anywhere you like? Z can be anywhere? the starting point. The starting point could be anywhere. Yeah. But when you actually run the algorithm, you uh you only go from -2 to 2.
于是我们现在做 Z 平方加 C。C 永远是初始的那个点。但是 Z 会不断变化。然后它映射到这里，举个例子。现在新的点就是 Z。然后你再做一次 Z 平方加 C。它映射到这边。所以，呃，我写了一个小程序来演示这个映射，以及它实际看起来是什么样子，是的。那 C 可以是任意位置吗？Z 可以在任何地方？起始点。起始点可以在任何地方。是的。但当你实际运行这个算法时，你呃只从 -2 到 2。
60:39
Uh -2 2. Because that's the only region in which interesting things happen with this fractal. So, I didn't finish explaining the algorithm. So, say a point in here, a point that's very close to the to the origin, 0 0. What it tends to do is spiral inward as you iterate it. But a point out here, what it tends to do or definitely a point outside of two, what it tends to do when you apply this function is to get mapped out here and to get mapped like over there and just go like really far away. So, what we do to to to render the Mandelbrot set is apply the function a number of times.
呃，-2 到 2。因为那是这个分形唯一会发生有趣现象的区域。所以，我还没讲完这个算法。那么，比如说这里面的一个点，一个非常靠近原点 0,0 的点。它往往会随着迭代向内螺旋。但是外面这里的一个点，它往往会——或者说肯定是二以外的点，当你应用这个函数时，它往往会被映射到这边，被映射到那边，然后就跑到非常远的地方去。所以，我们渲染曼德博集合的做法，就是把这个函数迭代应用很多次。
61:28
And if the point eventually goes outside this circle at the origin of radius two, sorry, it's a bad circle. If the point eventually goes outside of this circle, we stop performing the function because we know that after it gets outside, it's going to keep going forever out. It has escaped. It's called the escape iterations. The number of iterations it takes to escape outside of this circle. These are escape iterations. So, what we do is we color the point depending on its escape iterations. So, when we actually And the other part of it is if it never escapes, we color it black.
如果这个点最终跑出了这个以原点为圆心、半径为 2 的圆，抱歉，这个圆画得不太好。如果这个点最终跑出了这个圆，我们就停止继续迭代，因为我们知道它一旦跑出去之后，就会一直往外跑，永远不回来了。它逃逸了。这叫做逃逸迭代次数。也就是它跑出这个圆所需要的迭代次数。这些就是逃逸迭代次数。所以我们的做法是，根据一个点的逃逸迭代次数来给它上色。所以，当我们实际上——另一部分是，如果它永远不逃逸，我们就把它涂成黑色。
62:10
To actually test that, we just iterate a certain number of times, say like 500 times or like 70 times. And if it hasn't escaped after that many iterations, we sort of assume that it's never going to. It's not valid. So, it's it's an approximation to the actual set, but we have to do it to to render the actual thing. Then we color it black. So, when we actually render it, what we do is go through each pixel on the screen and apply this algorithm. So, for this point, this point becomes C. And we iterate, test, iterate, test, iterate, test. And what if the test what we're testing is if if it's outside of the circle. If it's outside of the circle, we assign it a color based on the number of iterations it took.
要真正判断这一点，我们就迭代固定的次数，比如说 500 次，或者 70 次。如果迭代了这么多次之后它还没逃逸，我们就大致认为它永远不会逃逸了。这不严谨。所以这只是对真实集合的一个近似，但为了把这东西渲染出来，我们不得不这么做。然后我们就把它涂成黑色。所以，实际渲染的时候，我们的做法是遍历屏幕上的每一个像素，对它应用这个算法。所以，对于这个点，这个点就成了 C。然后我们迭代、检测，迭代、检测，迭代、检测。我们检测的是它是不是跑到了圆外面。如果它在圆外面，我们就根据它所用的迭代次数给它分配一个颜色。
62:54
And we do that for each one. So, we keep going and say this one, for example, is going to spiral in. It's uh it's not a continuous line. It just applies the function. And it spirals in. So, that's that's never going to escape, so we're going to color it black. And this um this applet is excellent showing this. So, I I implemented this algorithm in Java. And um it it's going to output the the point and it's going to draw the lines between each point. So, say it starts here, it's going to draw a line here and here here here.
每一个点我们都这么做。我们继续往下走，比如说这个点，它会往里螺旋收敛。这个——它不是一条连续的线。它只是在不断应用这个函数。然后它就螺旋收敛进去了。所以这个点永远不会逃逸，那我们就把它涂成黑色。还有这个小程序，把这一点展示得非常好。我用 Java 实现了这个算法。它会输出这些点，并且在每两个点之间画出连线。比如说它从这里开始，它会画一条线到这里，再到这里、这里、这里。
63:42
So, what we're going to see is really cool. So, this is this is what we get in the end. And as I move my mouse around, it does these tests. So, here we can see that there's only one iteration. The one iteration gets the color light blue. And then here there are two iterations. And they're listed up there, one two. Um So, you can see all the way wherever it's this color, there are only two iterations before the point gets outside of this circle. Two two two, I think. So, as we go deeper in, there it it takes three iterations, four or five, six, seven.
所以我们将会看到非常酷的东西。这就是我们最终得到的结果。当我移动鼠标的时候，它就在做这些检测。在这里我们可以看到只有一次迭代。一次迭代得到的颜色是浅蓝色。然后在这里是两次迭代。上面也列出来了，一、二。嗯，所以你可以看到，凡是这个颜色的地方，都是只经过两次迭代这个点就跑出了这个圆。二、二、二，我想是这样。所以，随着我们越往里走，这里需要三次迭代，四次、五次、六次、七次。
64:22
A lot of iterations. So, all the points that that are colored, they do eventually escape. But all the points that are black don't escape. And so, the patterns that are inside are really interesting. See these in the middle, they just sort of spiral in. Keep going. Um the ones here, there's some looping pattern. See it? The function loops back on itself. So, it's sort of recursive. Like I don't really understand how it's recursive, but it sort of is. So, if you go out to this other nub, the second nub out, it gets this it's really cool shape.
迭代次数很多。所以所有有颜色的点，它们最终都会逃逸。但所有黑色的点都不会逃逸。而里面这些图案真的很有意思。看中间这些，它们就是一直往里螺旋。一直转下去。嗯，这边这些点，有一种循环的模式。看到了吗？这个函数绕回到了它自己。所以它有点递归的意思。我其实不太说得清它到底怎么个递归法，但它确实有那么点意思。如果你跑到旁边这个凸起上，也就是往外数第二个凸起，就会得到这个——形状真的很酷。
64:59
So, what we could do is zoom in actually on this. It redraws it. So, it's calculating this algorithm for every single point as we speak. It's doing it really fast. Um So, we can see all these really cool shapes that generate this fractal. And it's just just crazy.
我们可以做的是，实际放大这里看看。它会重新绘制。所以就在我们说话的这会儿，它正在对每一个点计算这个算法。速度非常快。嗯，所以我们能看到所有这些生成这个分形的超酷图形。简直太疯狂了。
65:31
So, we can sort of see recursion here. Like it looks like there's definitely some recursive thing going on. And the recursive part of this is the fact that um Z gets applied to itself. Z of it like this is the nth Z is equal to the Z that came before it squared plus C. And then this Z is reframed as the old Z. And this reframing and reapplying of the function is what makes it recursive. So, yeah, it sort of makes sense. Let's just go through the code quickly. And then I want to uh show some really cool things.
所以我们在这里多少能看出递归。看起来这里面肯定有某种递归的东西在发生。而这里面递归的部分在于，Z 被应用到了它自己身上。这个 Z——比如说第 n 个 Z 等于它前面那个 Z 的平方加上 C。然后这个 Z 又被重新当作旧的 Z。这种把结果重新代入、再次应用函数的做法，正是它递归的地方。所以，是的，这多少讲得通。我们快速过一遍代码吧。然后我想给大家看一些非常酷的东西。
66:20
Oh, where did it go? So, yeah, in the black part, it just recurses infinitely. And the code itself is not recursive, but the mapping function, again, is what's recursive. So, yeah, the black parts are in the set. So, the the real actual Mandelbrot set is just the black points. We just color the other points so it looks pretty. So, let's look at the code. Um def draw Mandelbrot. See that there? Um window.set -2 2. So, it just sets the window, the plotting range to be in this range. For for every X pixel in the height of the window or the width of the window and every Y pixel in the height, C.real and C.imaginary get the X and Y values on the screen.
哦，跑哪去了？所以是的，在黑色的部分，它就是无限地递归下去。代码本身并不是递归的，但那个映射函数，再强调一次，才是递归的那部分。所以，是的，黑色的部分属于这个集合。所以真正的曼德博集合其实只有那些黑色的点。我们给其他点上色只是为了好看。那我们来看代码。嗯，def draw Mandelbrot（绘制曼德博集合）。看到了吗？嗯，window.set -2 2。这只是设置窗口，把绘图范围设成这个区间。对于窗口宽度中的每一个 X 像素，以及高度中的每一个 Y 像素，C.real 和 C.imaginary 取的就是屏幕上的 X 和 Y 值。
67:17
So, what we're doing there is saying basically the pixel gets this actual point in the space that we're working the the the the complex plane. def iterations equals calculate iterations C. And we pass it C. Keep in mind, this is C. The starting point is C. So, let's just stay inside this function for now. def color equals calculate color iterations. So, we're calculating the color based on the number of iterations it took to escape. And then fill the pixel with the color. That plots it on the screen.
我们在那里做的事情，基本上就是说：这个像素对应到我们所处的这个空间——也就是复平面——里的这个实际的点。def iterations = calculate iterations C（迭代次数 = 计算迭代次数(C)）。我们把 C 传进去。记住，这就是 C。起始点就是 C。那我们先待在这个函数里面看。def color = calculate color iterations（颜色 = 根据迭代次数计算颜色）。所以我们是根据逃逸所用的迭代次数来计算颜色。然后用这个颜色填充这个像素。这就把它画到屏幕上了。
67:56
So, let's look at the calculate iterations function. int calculate iterations. This notation means that it will return an integer, a number. It takes a complex number C. So, Z.real, Z.imaginary start at zero. Start there. And then iteration starts off at zero. So, this is we're going to count how many iterations it takes. So, while the circle contains Z, that's another function that just tests if it's inside. Um and the number of iterations is less than max iterations. Max iterations is the number of iterations after which we assume it's it's just going to spiral inward just stay inside.
那我们来看 calculate iterations 这个函数。int calculate iterations。这个写法表示它会返回一个整数，一个数字。它接收一个复数 C。然后 Z.real、Z.imaginary 都从零开始。就从那里开始。然后迭代计数从零开始。所以我们要数一数它需要多少次迭代。所以，当这个圆还包含着 Z 时——那是另一个函数，就是判断它在不在圆里面。并且迭代次数小于最大迭代次数。最大迭代次数就是超过这个次数之后我们就假定它会一直往里螺旋、一直待在里面的那个次数。
68:39
Um So, while that stuff is true, Z equals Z squared plus C. Z equals Z times Z plus C, which is Z squared. So, we can do that because I I overloaded the operators, the multiplication and addition for complex number. So, it behaves correctly. It does this strange multiplication thing. And so, we do that, iterations plus plus. That means we increment the number of iterations by one. And uh calculate color just it calculates the color based on number of iterations. So, we have 20 minutes left. I want to uh blow you away with with some music and fractals.
嗯，所以在这些条件都成立时，Z = Z 的平方加 C。Z = Z 乘 Z 加 C，也就是 Z 的平方。我们能这么写，是因为我重载了运算符，重载了复数的乘法和加法。所以它的行为是正确的。它会执行那种奇特的乘法运算。然后我们这么做，iterations++。意思是把迭代次数加一。而 calculate color 就只是根据迭代次数算出颜色。我们还剩 20 分钟。我想用一些音乐和分形把大家震撼一下。
11巴赫的嵌套和声：递归结构与过程
69:28
So, I'm going to play a piece three pieces of Bach. And yeah, they're just great. So, the first one is actually not written by Bach. Oh, no. What's going on here? Uh it's not written by Bach, but it's the little harmonic labyrinth, which is the song that the dialogue in is based on. Carl Philipp Emanuel Bach. Sort of you know, English language has a grammar. We could nest sentences inside which we can nest more sentences. We could we we could nest more sentences. And that itself was a nested sentence.
我要弹一首——三首巴赫的曲子。是的，它们真的非常棒。第一首其实不是巴赫写的。哦不，这是怎么回事？呃，它不是巴赫写的，而是《小和声迷宫》，这首曲子正是那段对话所依据的原型。卡尔·菲利普·埃马努埃尔·巴赫。就好比说，英语是有语法的。我们可以在句子里嵌套句子，在里面还能再嵌套更多句子。我们还能再嵌套更多句子。而这句话本身就是一个嵌套句。
70:10
So, music sort of like English English has sort of a grammar to it. These chord progressions and melodies and you know, harmonies particularly have a sort of a language in which they can move between keys and whatnot. And um And so, that that's one way in which Bach embeds recursion inside of music. He has these nested um harmonic structures of chord progressions. So, the chord it's yeah, in in chapter five of Carl Philipp Emanuel Bach, he talks about it. And the dialogue is modeled after uh that first song that we heard, little harmonic labyrinth. And melodies also can sort of have recursion in that they can have patterns.
所以音乐有点像英语，英语有它的语法。这些和弦进行、旋律，还有和声，尤其是和声，都有一套自己的语言，让它们能够在不同调性之间转换等等。所以，这就是巴赫在音乐中嵌入递归的一种方式。他用的是这些嵌套的和声结构、和弦进行。所以那个和弦——是的，在《卡尔·菲利普·埃马努埃尔·巴赫》的第五章里，他谈到了这一点。而那段对话正是仿照我们刚才听到的第一首曲子《小和声迷宫》写的。旋律也可以带有某种递归性，因为它们可以有各种模式。
70:57
Um like this theme for example. This theme like Bach does this a lot. What he does is he takes themes and he restates them with maybe different harmonies. And uh they embeds them inside smaller and larger scales. So, for example, I don't know if he did this did did this like maybe on a larger scale um the the actual harmony might actually follow this sort of theme. And inside those, you know, like for a long period of time be this key and long period of time be this key. And then when you're in that key he he plays this theme.
嗯，比如说这个主题。这个主题——巴赫经常这么干。他会拿一个主题，然后用不同的和声把它重新陈述一遍。然后他把这些主题嵌套在更小和更大的尺度里。比如说，我不知道他有没有在更大的尺度上这么做过，嗯，整体的和声走向说不定真的会遵循这个主题的形状。而在这些内部，比如说很长一段时间处在这个调上，再很长一段时间处在这个调上。然后当你处在那个调里的时候，他就会演奏这个主题。
71:41
So, that's an example of nesting. So, recursion per se is not there, but the result of a recursion. This is the distinction between recursive processes and recursive structures. Recursive structures are basically any structure that has nesting to it. So, English language is recur- is a recursive structure because it comes from a recursive grammar. It has nesting. And music also it's a recursive structure, not a recursive process. So, recursive process is like almost like a function that defines how you can get the recursive structure.
所以这就是嵌套的一个例子。所以严格来说递归本身并不在那里，在那里的是递归的结果。这就是它们的区别所在递归过程和递归结构之间的区别。递归结构基本上就是任何带有嵌套的结构。所以，英语是递归的——是一种递归结构，因为它来自递归语法。它有嵌套。而音乐也是一种递归结构，不是递归过程。所以递归过程差不多就像一个函数，它定义了你怎么得到这个递归结构。
72:15
Exactly. That's it. He said so, a recursive process is sort of like a function or something that defines how you end up with a recursive structure. That's exactly it. Yeah. So, so he he's just playing like overall there's this whole theme and he chooses some parts of that theme that he also plays. And then he plays like that and then he gets out of that part of it and then he goes to another one which is also part of the Yeah. Yeah. But it's hard to hear cuz it's Yeah, it's hard to hear. It takes a really fine musical ear to hear this.
没错，就是这样。他说，递归过程有点像一个函数或者别的什么东西，它定义了你最终怎么得到一个递归结构。完全正确。对。所以，所以他就是在弹，整体上有这么一个主题，然后他挑出这个主题的某些部分，那些部分他也会弹。然后他那样弹一段，接着从那部分里出来，再进到另一段，而那一段同样是……的一部分。对。对。但是很难听出来，因为——对，很难听出来。要听出这个得有非常敏锐的音乐耳朵。
12调用栈的压入弹出与音乐迷宫
72:49
And uh uh so, let's see how how much time. 3 minutes. So, um We talk about pushing and popping of stacks. So, a function, a computer function say F foo actually. Foo is a function. Or better yet, well, no, forget forget it. And inside this foo, it calls the function bar. And here's a function bar. It does some stuff and it calls maybe G. It does some other stuff and here's G. G maybe does just one thing and I don't know ends. So, what you have is a stack a a call stack. Like it it happens in in in any grammar actually that's that's sort of recursive flow. So, in computer programs and also in English, you have this notion of a stack. So, here you do some stuff, you do some stuff.
呃，我们看看还有多少时间。3分钟。那么，嗯，我们讲讲栈的压入和弹出。所以，一个函数，一个计算机函数，比如说 F，其实叫 foo 吧。foo 是一个函数。或者更好的是——嗯，不，算了算了。然后在这个 foo 里面，它调用了函数 bar。这里是函数 bar。它做一些事情，然后它可能调用 G。它再做一些别的事情，这里是 G。G 可能只做一件事，然后我不知道，就结束了。所以你得到的是一个栈，一个调用栈。其实在任何语法里都会发生，只要是那种递归式的流程。所以在计算机程序里，还有在英语里，你都有栈这个概念。所以在这里你做一些事，你做一些事。
74:05
And when you call bar your focus actually changes to over here, bar. But you retain sort of in your mind or in the in the memory of the computer where you were, where you left from. So, you you yeah. Is this like when you do when you're like trying to do something even like maybe have several songs and so on and so on? Calls? When have goals. Goals. Yeah, exactly. So, that's that's why computer programming is tough because like you have a a high level goal, but then to get to that goal just like you said, you have other goals that you need to meet and each of those goals requires some other goals. So, it's actually recursive. Like It's crazy. So, when you when this func- when this when this program executes, it does this stuff.
然后当你调用 bar 的时候，你的注意力其实转移到了这边，bar 这里。但你在脑子里，或者在计算机的内存里，保留着你刚才在哪儿、你是从哪儿离开的。所以你——对。这是不是就像你在做某件事的时候，比如你可能有好几首歌之类的，一层套一层？调用？当你有目标的时候。目标。对，正是这样。所以，这就是为什么计算机编程很难，因为你有一个高层的目标，但要达到那个目标，就像你说的，你还有别的目标要完成，而那些目标里的每一个又需要一些别的目标。所以它其实是递归的。就像——太疯狂了。所以当这个函数——当这个程序执行的时候，它做这些事。
74:51
It puts this position A, let's say, on the stack. So, this is the stack. A. And then it goes into here, bar. Blah blah blah. Does all this stuff. Then it calls G. But to remember where this is, let's call this position B. It puts B on the stack. And calls G and then does all this stuff. And then after this it returns. And when it returns, it asks, "Where was I last time?" And this is what the stack is for. So, "Where was I last time?" I was at B. So, we pop. Putting something on the stack is pushing. Taking off is called pop.
它把这个位置，就叫 A 吧，放到栈上。所以这就是栈。A。然后它进到这里，bar。啦啦啦。做完所有这些事。然后它调用 G。但为了记住这里是哪儿，我们把这个位置叫 B。它把 B 放到栈上。然后调用 G，接着做完所有这些事。然后在这之后它返回。当它返回的时候，它就问：“我上次在哪儿来着？”这就是栈的用处。所以，“我上次在哪儿来着？”我在 B。所以我们弹出。把东西放到栈上叫压入（push）。取下来叫弹出（pop）。
75:26
We pop it and say, "Okay, here's B." This is B is where we were. We go back to there. And we we finish this. Once we finish this, we say, "Oh, where were we last time?" So, it gets A. And then go back to A and finish. Yeah. So, so you you can like make it so that you have those things, right? Those are like themes maybe like parts of the music, right? Yeah, sure. Yeah, I mean yeah, exactly. other things that that thing sort of like reflects itself. Yeah. Yeah. So, the dialogue which reflects little harmonic labyrinth has this sort of structure. It goes inside something inside yet another thing and back out and then back up. So, so it's 5:00. I'm finished.
我们把它弹出来，说：“好，这是 B。”这个 B 就是我们刚才所在的地方。我们回到那儿。然后我们把这部分做完。做完之后，我们说：“哦，我们上次在哪儿来着？”于是它取到 A。然后回到 A，把它做完。对。所以，所以你可以把它做成这样，让你有那些东西，对吧？那些就像是主题，可能是音乐的某些部分，对吧？对，当然。对，我是说，对，正是这样。别的东西，那个东西有点像是在反射自身。对。对。所以那段呼应《小和声迷宫》的对话就有这种结构。它进到某个东西里面，再进到另一个东西里面，然后出来，再回到上一层。所以，5点了。我讲完了。
视频总结 · 一句话概括与核心要点
一句话概括
代课讲师 Curran Kelleher 通过一系列递归程序（阶乘、斐波那契、递归转移网络、分形树、Koch 曲线、Sierpinski 三角形、分形蕨、Mandelbrot 集）说明递归如何产生嵌套与分形，并区分"递归过程"与"递归结构"，最后引申到语言、巴赫音乐和调用栈。
核心要点
- 递归函数的本质是"调用自身 + 终止条件"：阶乘定义为 n! = n × (n−1)!，代码为 `if n > 1: return n * factorial(n-1) else: return 1`；斐波那契同理 fib(n) = fib(n−1) + fib(n−2)。若去掉 `n > 1` 的判断，函数会无限自我调用，因此所有可执行的递归都必须"触底"（bottom out）。自然界的树也会在分支足够小时生成叶子而停止。
- 自然语言的语法本身就是递归的：讲师把 GEB 第 132 页的递归转移网络（RTN）直接翻译成程序——图中每条箭头对应一个函数调用，"fancy noun"节点会再次调用自身。随机选择转移路径可生成 100 个句子，如"the small bagel inside the strange cow"，有些合乎语法但无意义。递归导致嵌套，嵌套（可能无限）正是分形的来源。
- 分形树只需两条自调用即可生成：`growTree` 画一条线后调用自身两次，长度乘以 0.58 左右的缩放因子，角度各偏 ±π/4（45°），深度参数每层减一直到 0（示例深度 11）。若深度取无穷，图形可无限放大且各尺度形态相同——这就是分形的定义。
- Koch 曲线、随机化后即成海岸线和山脉：规则是把线段三等分，中段替换为等边三角形的两边；代码中 `createCurve` 对四个子段各调用一次自身。若在每次迭代中给顶点加入少量随机扰动，二维结果酷似海岸线，推广到三维则生成逼真的山体表面。
- Koch 雪花面积有限而周长无限：每次应用规则周长都变长，无限迭代后周长发散但围住的面积收敛。学生提问"把它剪开拉直会怎样"，讲师答：会无限延伸。由此引出"英国海岸线长度"问题：放大越细，测得的长度越长，因此无法给出确定值；但这只是数学理想，物理世界中不存在真正无限的周长，海岸线只是近似。
- Sierpinski 三角形可由"混沌游戏"生成，代码本身不递归：从任意点出发，随机选三个顶点之一并移动到中点（`(current + next) / 2`），在 `while true` 循环中不断绘点。无论随机序列如何，最终图像总是相同的 Sierpinski 三角形。
- 分形蕨是四个仿射映射的迭代函数系统（IFS）：四个映射分别对应茎、左叶、右叶、"向上卷曲"，选择概率为 0.01、0.07、0.07、0.85。若概率均等，向上映射连续发生多次的机会极低，图像会稀疏难看。递归性不在代码里，而在映射本身：每个子区域是整体的缩小副本，整体又被反复映射回子区域。
- Sierpinski 与蕨在本质上相同：三角形的"走到顶点中点"等价于把大三角映射到三个子三角，概率各 1/3。因此"递归"存在于更高抽象层次——必须"跳出系统"进行整体推理才能看出，目前没有一种机械测试能仅凭代码判断输出是否递归，这是人类而非计算机的能力。
- Mandelbrot 集是复平面上 Z = Z² + C 的逃逸迭代：每个像素作为 C，Z 从 0 开始迭代；若 |Z| 超过半径 2 的圆就判定"逃逸"，按逃逸迭代次数着色；在最大迭代次数（如 70 或 500）内未逃逸则涂黑，黑色部分才是真正的集合。绘制范围取 −2 到 2，因为有趣的行为只发生在这一区域。递归性在于新 Z 被重新当作旧 Z 反复代入。
- 递归过程 vs. 递归结构，以及调用栈：英语和巴赫音乐是"递归结构"（有嵌套），而非"递归过程"；递归过程是生成递归结构的规则。巴赫在和声（调性嵌套）与旋律（主题在不同尺度上重述）两个层面嵌入嵌套。函数 foo 调用 bar、bar 调用 G 时，返回位置依次被压栈（push），返回时弹栈（pop）——这与 GEB《小和声迷宫》对话"进入-再进入-退出-再退出"的结构一致，也与人类完成目标时的子目标层级相同。
结论与值得注意的细节
- 全讲的核心命题：递归 → 嵌套 → 分形，而递归可以出现在代码层（自调用函数），也可以只出现在数学映射层（IFS、Mandelbrot 迭代），后者需要抽象思维才能识别。
- 讲师反复强调数学上的无限分形是理论构造，自然界（树、海岸线、山脉）只是有限层数的近似，但相似度惊人。
- 讲座中投影仪和 Groovy 程序演示多次失败，讲师主要靠板书讲解；仅 Mandelbrot 的 Java applet 成功演示了逐点迭代与缩放。
- 讲师承认自己"不完全理解 Mandelbrot 集如何是递归的"，只能指出迭代中的自我代入是递归性来源。
- 学生提出的两个关键问题值得记住：一是"同一算法总有多种表示方式"（如 Sierpinski 的几何规则与混沌游戏），二是"若代码无递归函数，如何不运行就判断输出是递归的"——答案是必须跳出系统做高层推理。
核心句型 · 9
1. What makes X Y is the fact that …
“What makes this function recursive is the fact that it calls itself”
用 the fact that 把「原因」名词化，适合下定义或点明本质特征。仿写：What makes this argument convincing is the fact that it relies on data.
2. X is defined in terms of itself
“Recursion is something which is defined in terms of itself”
in terms of 表示「用……来定义/表述」。学术写作中描述循环定义、相对关系时常用。仿写：Success here is defined in terms of user retention.
3. You could imagine if you were to …, …
“You could imagine if you were to continue this infinitely”
were to 虚拟语气引出假想情境，语气比 if you continue 更客气、更思辨。适合引导听众做思想实验。
4. The more you …, the longer/more … gets
“The more that you zoom in on the coast of Britain, the longer the perimeter gets”
双重比较级表示正相关关系。注意口语中可加 that；书面省略。仿写：The more precisely you measure, the longer it gets.
5. Let's hold off on that until after we …
“Let's hold off on that answer until after we do the next one”
hold off on 表示暂缓。讲课或汇报时把问题悬置到后面再答的地道说法，比 wait 更自然。
6. X per se is not there, but the result of X is
“Recursion per se is not there, but the result of a recursion”
per se 强调「就其本身而言」，用于区分「事物本身」与「事物的效果/表现」。适合做概念辨析。
7. This is the distinction between A and B
“This is the distinction between recursive processes and recursive structures”
点明两个概念的区别，常在给出例子后总结用。后接对 A、B 各自的定义句。
8. It takes a really … to …
“It takes a really fine musical ear to hear this”
it takes + 名词 + to do 表示「做某事需要某种能力/条件」。仿写：It takes a trained eye to spot the difference.
9. in order to do anything, X has to …
“All recursive functions in order to do anything have to bottom out at some point”
用「要想有任何结果」强调必要条件，语气比 must 更带论证味。仿写：In order to be useful, a model has to generalize.
词汇精讲 · 92 · 按出现顺序
recursion
/rɪˈkɜːrʒən/
n.
0:00
递归；自我调用或自我指涉的过程
fractals
/ˈfræktəlz/
n.
0:00
分形（局部与整体自相似的几何图形）
fill in
phr.
0:00
代班，临时顶替
self-similar
/ˌselfˈsɪmələr/
adj.
0:40
自相似的，各尺度下形态相同的
factorial
/fækˈtɔːriəl/
n.
0:40
阶乘
argument
/ˈɑːrɡjəmənt/
n.
2:40
（函数的）参数、实参
transition networks
n. phr.
6:54
转移网络（由节点和有向边构成的语法图）
grammar
/ˈɡræmər/
n.
6:54
（形式）语法，生成规则系统
essence
/ˈesns/
n.
6:54
本质，精髓
loops back out on itself
phr.
7:50
绕回到自身，形成环路
at random
phr.
7:50
随机地
curly braces
n. phr.
8:32
花括号 { }
preposition
/ˌprepəˈzɪʃn/
n.
9:29
介词
relative pronoun
n. phr.
9:29
关系代词（who, which, that 等）
correspond to
phr.
9:29
与……对应
nest
/nest/
v.
10:10
嵌套，把一层结构放入另一层之内
pseudo code
/ˈsuːdoʊ koʊd/
n.
11:41
伪代码，用自然语言写的算法草稿
entry point
n. phr.
12:04
（程序的）入口点
initiates
/ɪˈnɪʃieɪts/
v.
12:04
启动，发起
branch out
phr.
13:16
分枝，向外扩展
scale
/skeɪl/
v.
14:09
按比例缩放
zoomed in on
phr.
16:04
放大观察（zoom in on sth）
equilateral triangle
/ˌiːkwɪˈlætərəl ˈtraɪæŋɡl/
n. phr.
16:50
等边三角形
segments
/ˈseɡmənts/
n.
16:50
线段，分段
execution
/ˌeksɪˈkjuːʃn/
n.
17:35
（程序或规则的）执行
generalize
/ˈdʒenrəlaɪz/
v.
19:25
推广，一般化
randomization
/ˌrændəmaɪˈzeɪʃn/
n.
20:10
随机化
coastlines
/ˈkoʊstlaɪnz/
n.
20:10
海岸线
extrapolated
/ɪkˈstræpəleɪtɪd/
v.
21:04
外推，由已知推断未知
perimeter
/pəˈrɪmɪtər/
n.
21:04
周长
finite
/ˈfaɪnaɪt/
adj.
21:04
有限的（反义 infinite）
mind-boggling
/ˈmaɪnd ˌbɑːɡlɪŋ/
adj.
21:40
令人难以置信的，难以想象的
iterations
/ˌɪtəˈreɪʃnz/
n.
21:40
迭代，重复执行的次数
satellite image
n. phr.
24:06
卫星图像
line up
phr.
24:06
对齐，吻合
refine
/rɪˈfaɪn/
v.
24:39
细化，使更精确
theoretical creation
n. phr.
25:44
理论构造物
resembles
/rɪˈzemblz/
v.
26:21
与……相似
iterated function system
n. phr.
27:22
迭代函数系统（IFS），由多个收缩映射反复作用生成分形
chaos game
n. phr.
28:08
混沌游戏（随机向顶点移动一半距离的分形生成法）
plot
/plɑːt/
v.
28:48
绘制（点或曲线）
fern
/fɜːrn/
n.
30:08
蕨类植物
hold off on
phr.
32:16
推迟，暂缓（做某事）
bottom out
phr.
34:11
触底；（递归）到达终止条件
manifestation
/ˌmænɪfeˈsteɪʃn/
n.
34:51
显现，具体表现
well put
phr.
36:08
说得好，表述精当
coordinate transformation
n. phr.
37:26
坐标变换
outer
/ˈaʊtər/
adj.
39:14
外层的，外部的
maps to
phr.
39:53
映射到
correspond
/ˌkɔːrəˈspɑːnd/
v.
44:52
对应，相当
probabilities
/ˌprɑːbəˈbɪlətiz/
n.
48:25
概率
sparse
/spɑːrs/
adj.
48:25
稀疏的
spiraling
/ˈspaɪrəlɪŋ/
v.
49:06
盘旋，呈螺旋状运动
repetitive
/rɪˈpetətɪv/
adj.
50:46
重复性的
extrapolating
/ɪkˈstræpəleɪtɪŋ/
v.
52:38
外推，推演
stepping out of the system
phr.
52:38
跳出系统（GEB 术语：从更高层次审视系统）
abstract from
phr.
53:15
从……中抽象出来，忽略细节
perceive
/pərˈsiːv/
v.
53:15
感知，觉察
complex plane
n. phr.
56:07
复平面
mathy
/ˈmæθi/
adj.
56:07
（口语）数学味浓的，偏数学的
imaginary
/ɪˈmædʒɪneri/
adj.
56:55
虚（数）的
square root
n. phr.
56:55
平方根
linear
/ˈlɪniər/
adj.
58:16
线性的
components
/kəmˈpoʊnənts/
n.
59:09
分量，组成部分
applet
/ˈæplət/
n.
59:53
小应用程序（尤指嵌入网页的 Java 程序）
origin
/ˈɔːrɪdʒɪn/
n.
60:39
（坐标）原点
render
/ˈrendər/
v.
60:39
渲染，绘制成图像
radius
/ˈreɪdiəs/
n.
61:28
半径
escaped
/ɪˈskeɪpt/
v.
61:28
逃逸（此处指迭代点跑出边界圆）
approximation
/əˌprɑːksɪˈmeɪʃn/
n.
62:10
近似
assign
/əˈsaɪn/
v.
62:10
分配，指定
nub
/nʌb/
n.
64:22
小突起，小疙瘩
reframed
/ˌriːˈfreɪmd/
v.
65:31
重新框定，重新设定为
recurses
/rɪˈkɜːrsɪz/
v.
66:20
递归调用
integer
/ˈɪntɪdʒər/
n.
67:56
整数
overloaded
/ˌoʊvərˈloʊdɪd/
v.
68:39
（编程）重载（为运算符定义新含义）
increment
/ˈɪŋkrəmənt/
v.
68:39
递增，加一
blow you away
phr.
68:39
让你大为震撼
harmonic
/hɑːrˈmɑːnɪk/
adj.
69:28
和声的
labyrinth
/ˈlæbərɪnθ/
n.
69:28
迷宫
chord progressions
n. phr.
70:10
和弦进行
keys
/kiːz/
n.
70:10
（音乐）调，调性
embeds
/ɪmˈbedz/
v.
70:10
嵌入
modeled after
phr.
70:10
以……为原型仿制
restates
/ˌriːˈsteɪts/
v.
70:57
重述，再次陈述（音乐主题）
per se
/ˌpɜːr ˈseɪ/
adv.
71:41
本身，就其本身而言（拉丁语）
distinction
/dɪˈstɪŋkʃn/
n.
71:41
区别，区分
fine musical ear
n. phr.
72:15
敏锐的音乐听觉
pushing and popping
phr.
72:49
（栈的）压入与弹出
call stack
n. phr.
72:49
调用栈
retain
/rɪˈteɪn/
v.
74:05
保留，记住
reflects
/rɪˈflekts/
v.
75:26
映照，反映
理解自测 · 11 题
1. 讲者一开始给递归函数下的定义是什么？用阶乘举例说明。
讲者的初始定义是「递归函数就是调用自身的函数」。以阶乘为例，n! 被定义为 n × (n−1)!，程序中 factorial(n) 内部调用 factorial(n−1)，当 n 大于 1 时不断向下调用，直到 n 等于 1 返回 1，再逐层相乘得到结果。这一定义出现在开场的阶乘与斐波那契部分，是全讲的出发点；后面讲者会用谢尔宾斯基三角形和蕨类的例子修正它。
2. 科赫曲线的生成规则是什么？程序 create curve 为什么要调用自己四次？
规则是把一条线段三等分，在中段上向外做一个等边三角形，并去掉原来的中段，于是一条线段变成四条较短线段。程序 create curve 调用自身四次，正是因为每次应用规则后产生四段，每一段都要再次应用同样的规则。讲者在科赫曲线一节中把代码里四个函数调用与图上的四段一一对应，说明程序结构直接映射几何规则。
3. 分形蕨的四个映射分别对应什么，概率各是多少？
四个映射分别对应：映射到茎（概率 0.01）、映射到左分枝（0.07）、映射到右分枝（0.07）、向上盘旋的主体映射（0.85）。讲者在蕨类一节解释，这些概率只影响点的分布密度和图像饱满度，不改变最终形状；他试过等概率，结果上部极其稀疏，「看起来很不好」。这正是 Barnsley 蕨的标准参数。
4. 为什么讲者说所有递归函数都必须「触底」（bottom out）？
因为递归函数每次都调用自身，如果没有终止条件（如 n ≤ 1 时返回 1，或 depth 为 0 时停止），它会无限调用下去，永远返回不了结果。在学生提问环节，讲者以去掉判断条件的 Fibonacci 为例说明会无限循环。他同时指出自然界的递归（如树的分枝）也会在枝条达到某个尺寸时转为生叶而停止，只有理论世界（如 GEB 里精灵问元精灵的对话）才能设想不触底的递归。
5. 科赫雪花为什么面积有限而周长无限？讲者如何回应学生「碎片越来越小应该收敛」的疑问？
每次应用规则周长都变为原来的 4/3，无限次后周长发散到无穷；而面积增量越来越小且总和收敛，整个图形始终装在一个有限的框内。学生质疑新增的碎片越来越小、总长应该收敛，讲者的回答是：对分形而言，每层新增的长度并不趋于零，所以总和不断变大，「越精确越长」。他借英国海岸线的例子说明这是同一现象：测量尺度越小，海岸线越长，因此从来没人能定出确切数值。
6. 谢尔宾斯基三角形的混沌游戏是随机的，为什么每次生成的图像都一样？
因为三个「向顶点移动一半距离」的映射构成一个迭代函数系统，它们有唯一的吸引子——谢尔宾斯基三角形。无论初始点在哪、随机序列如何，点经过多次映射后都会落在吸引子上并逐渐填满它。讲者在回答学生「重新运行会不会不同」时明确说答案是「会生成同样的图」，并在蕨类例子之后进一步解释：每个映射把整体缩到局部，整体又包含所有局部，所以结构被无限复制，与具体随机路径无关。
7. 讲者说「代码本身不递归，但映射是递归的」，这句话如何改变了递归的定义？
它把递归从「函数调用自身」这一代码层面的特征，扩展为「结构把整体映射到自身的一部分」这一更抽象的属性。谢尔宾斯基三角形和蕨类的程序只是 while true 循环加随机选择，没有任何自调用，但三角形被映射到自身的三个子三角形、蕨叶被映射到自身的分枝上，这种「映射到自身」才是递归所在。这一转折为后面讨论英语和音乐做铺垫：它们是递归结构，未必由递归过程直接生成。
8. 在问答中，学生问「没有递归函数时如何不运行代码就判断输出是递归的」，讲者的回答与 GEB 的哪个概念相连？
讲者的回答是必须「跳出系统」：不能只在代码内部按步骤执行（那就是当一台计算机），而要从更高层次抽象地思考这些映射整体上在做什么，才能预见输出会是递归结构。这直接对应 GEB 中「跳出系统」（jumping out of the system）的概念。讲者进一步断言，没有严格的机械测试能判定一个程序会否产生递归输出，「目前只有人类能做到」，这与程序高层性质不可判定的思想相通。
9. 曼德博集合的渲染算法为何只在 −2 到 2 的范围内计算，并且用「逃逸迭代次数」上色？
数学上可证明，一旦迭代点的模超过 2，后续必然发散到无穷，所以半径 2 的圆是判定逃逸的边界，有趣的结构也只出现在这个范围内。算法对每个像素取 C，从 Z=0 开始反复计算 Z=Z²+C，记录跑出圆所需的迭代次数并据此上色；若达到最大迭代次数仍未逃逸，就假定它永不逃逸并涂黑。讲者强调这是近似：真正的集合只有黑色部分，彩色只是为了好看，而最大迭代次数是不得已的阈值。
10. 如果有人反驳「分形只是数学游戏，与现实无关」，讲者会如何回应？
讲者在课堂上已经预先回应了这一点。他承认数学上的科赫曲线是理论构造，宇宙中不存在真正无限精细的东西（地球空间有限）。但他同时指出自然界「相当接近」它：随机化的科赫规则生成的曲线与真实海岸线几乎一样，推广到三维就是逼真的山脉；树的分枝是一种运行中的递归程序；英国海岸线的长度随测量尺度增长且无法定值。因此他的立场是：分形是理想模型，其价值在于揭示自然结构在很宽尺度范围内的自相似规律，而非声称自然是无限的。
11. 讲者把调用栈与巴赫音乐的嵌套转调类比。这一类比放到日常任务规划中是否成立？
成立，而且讲者和学生在课堂末尾已经把它推广到了目标层面。调用栈的逻辑是：进入子任务前把当前位置压入栈，完成后弹出并回到原处；巴赫的《小和声迷宫》从主调进入某调、再进入更远的调，然后逐层返回，结构相同。学生提出「有目标时也是这样」，讲者认同：高层目标需要子目标，子目标又需要子子目标，这就是编程困难的根源。类比的限度在于：栈要求严格的后进先出，而人类的目标追求常常并行、中途放弃或忘记返回——这正是 GEB 所说的「层数太深会忘了自己在哪」。
下载便签
手机：长按图片也可保存
← 上一期 · NO.014Terence Tao at IMO 2024: AI and Mathematics
下一期 · NO.016 →Why This Is the Most Exciting Time to Be Human | Ken Ono, Axiom Math
订阅苏菲周报
每周一封：本周入库的精读、一个值得带走的问题、一条苏菲按。免费，随时退订。
免费 · 每周一封 · 一键退订
苏菲拉底
THE SOPHIE LAB · ASK THE BEST MINDS THE BIG QUESTIONS
内容仅供学习 · thesophielab.com