关于此实验
树由一段树干和上方的两棵小树组成。这一句话就是一个完整的程序：一个绘制树枝后再调用自身两次的函数。递归能用简短的规则生成丰富的图像。观察一棵树、一个谢尔宾斯基三角形和一片科赫雪花如何随着一次次调用逐渐构建，跟踪调用栈的增长与缩小，并数数随着深度增加，调用次数会以多快的速度激增。
学习目标
- 识别递归函数的基本情况和递归情况
- 跟踪递归调用执行和返回的顺序
- 说明调用栈中存放的内容，以及栈的深度为何重要
- 计算给定深度对应的调用次数，例如二叉树中的 2^(n+1) − 1
- 描述自相似性，并计算一个简单的分形维数
使用方法
- 1选择深度为 3 的树，慢慢观察调用过程。左分支和右分支中，哪一个先绘制？为什么？
- 2在栈达到最深处时暂停。栈中的每个帧代表什么？与深度相比，帧的数量是多少？
- 3填写树的深度与调用次数对照表。找出规律，并在深度为 10 时进行验证。
- 4更改分支角度和长度比例。哪些设置会使分支重叠？
- 5切换到谢尔宾斯基三角形。代码中的基本情况在哪里？深度为 5 时会绘制多少个三角形？
- 6构建深度为 5 的科赫雪花。利用读数说明周长如何不断增长，而面积仍然有限。
模型
假设
- 这些调用按照程序中的顺序一次执行一个，采用深度优先方式，与普通编程语言执行它们的方式完全相同。
- 伪代码将位置和方向作为参数传递，因此调用返回后无需恢复海龟的状态。
- 树的分形维数 log 2 / log(1/r) 只描述枝梢，且前提是树枝之间没有重叠。
- 为确保逐步回放仍然快速运行，我们限制了最大深度：树为 12，三角形为 7，雪花为 6。
在课堂上试试这个实验
- Q1如果树函数没有基本情况，会发生什么？
- Q2在深度为 4 时，谢尔宾斯基函数会进行多少次调用？请用一个和来解释答案。
- Q3尽管进行了数千次调用，为什么调用栈的深度始终不会超过递归深度加一？
- Q4编写一个计算 n! 的递归函数，并指出它的基本情况。
- Q5测量英国海岸线时，使用的尺子越短，测得的海岸线就越长。科赫雪花如何解释这一现象？
常见问题
递归比循环慢吗？
每次调用都会为栈帧消耗少量时间和内存，因此循环通常会稍快一些。但对于树、嵌套文件夹或语法解析等分支结构，递归编写起来要简单得多，而且任何递归都可以改写为使用自己显式维护的栈。
什么是栈溢出？
每个尚未完成的调用都会在调用栈中保留一个栈帧。如果递归过深，例如始终无法到达基本情况，栈内存就会耗尽，程序会因栈溢出错误而崩溃。
自然界中的分形有哪些？
蕨类植物、罗马花椰菜、河流网络、闪电、血管以及肺部呈分支状的气道，在多个尺度上都近似具有自相似性。因此，计算机图形学会使用递归规则来生成它们。