循环、递归与魔术（一）——递归与循环的数理逻辑

“

今天我们开启一段新的旅程，聊聊循环（circulation）和递归（recursion）背后的数理逻辑以及艺术应用。

”

循环和递归本是程序设计中常见的两种代码结构，其中循环对应的数学描述为迭代，递归即为嵌套自身。而二者共同的特性在于必须存在一种跳出机制：循环必有break，而递归必有对最简单情况的直接求解的返回。

另一方面，这种严格的逻辑结构，也给一些艺术创作赋予了灵感。比如在一些绘画，建筑等作品里，会用循环够早的周期性结果构造一种统一的美感，用递归结果的自相似特性构造一种无尽的想象，当然有时候还有对称，这是一种复合函数的周期性。不信你看下图：

图1/2/3 泰姬陵建筑上的循环，递归与对称

图4 分形之谢尔宾斯基(Sierpinski)三角形

我们的大脑天然对这种有一定规律的东西感到可以掌控和舒适。

还有在文学作品中，也经常用同而不犯的手法进行情节的推进设计，在相类似事物的序列循环基础上形成递进，起伏等手法以加深表达效果。又比如电影也会通过情节的相似重复来强化表达，歌曲里更是在高潮处要把同一句词唱很多遍，而这些方法也被一定程度上用在了魔术流程的设计中。

甚至在搜索引擎里，google也埋了彩蛋，调皮了一把：

图5 google递归一词

这一讲我们先聊聊循环和递归的数理逻辑，探究其数学本质和在程序中的应用；下一讲开始我们来给几个魔术上的例子，进一步看这个理念是如何利用在魔术这种艺术作品中的。

我们首先看一下基本定义：

循环：循环是程序设计语言中反复执行某些代码的一种计算机处理过程，常见的有按照次数循环和按照条件循环。

递归：程序调用自身的编程技巧称为递归，必须包括自调用和跳出条件。

而这个定义在逻辑上其实有两层理解：

循环和递归的数理逻辑

在人脑概念层面，循环是一个结构类似对象的序列，本身是一个线性结构，没有纵深的层次嵌套。我想，它用展开的一列扑克牌来表达其意思应该再合适不过了：

图6 扑克牌序列与循环

而递归其实是一种参数化简，形式不变的一种化归思想。即我要想一种方法，能够把原问题Pn变成包含它的问题Qn，而Qn是很好由参数更小的Qm来解决的。这种思想是一种计算机自顶向下思维方式的典范。使得大规模的问题可以放心地用这类思路来解决。如果用图来表达的话，看起来是这样子的：

图7/8 递归自相似的嵌套结构

这种图我记得第一次看到是在妈妈给我买的一包饼干上，上面有个小女孩拿着一包一样的饼干，饼干上又有一个小女孩拿着一样的饼干，饼干上……，当时我就惊讶于这种无限循环的图是怎么画出来的？盯着看了好几层直到变成一个点也没想明白，不会递归就是笨啊！

大家自己拿起两面镜子互相照一下应该就能够看到无限递归下去缩小的影像，如果大家以前上课的教室里有投影屏幕，投影的是摄像头拍摄屏幕的内容的话，就也会看到类似的画面。当时我看到这一场面还有点害怕，生怕像计算机出现死递归一样投影仪要爆炸了，但是又怎么会呢？投影仪根本不懂它近似投影的是什么整体内容，只是像素点而已。

还有一个解释递归的例子，说递归是包子馅的包子，极限则是馒头。这甚是巧妙，用人类已有的经验知识构造了一个递归的概念：有这么个东西，它用面皮包着自己。

循环和递归的程序逻辑

上面是人脑对循环和递归结构的抽象理解。然而所谓放心地解决，是指的只要把问题逻辑理清楚，转化为循环或者递归逻辑就能够写成代码执行，但执行本身是编译器的事，高级语言可以不关心。但仍然可以去窥探一下区别，毕竟你每日安好，其实是有人替你负重前行了。

在计算机执行层面：循环语句在高级语言中一般由类for和while语句来表示，在汇编语言中对应的就是命令行之间的有条件goto跳转（无条件的话就是死循环了），使得每次都会执行同样的代码但是由于前后有状态依赖，比如循环变量值的改变，因此执行内容是逻辑类似但是内容不同的。这对应的恰好就是我们在面对类似的样本序列或者迭代求值时候所需要的逻辑，其中前者往往是固定循环次数，前后无关联还可以并行；后者则有可能难以确定循环次数。这两种循环的模型在汇编代码上没有区别，但是就是否能固定次数来讲，还是有微妙的差别。

而递归则没有特殊的关键字，而只要出现了函数定义中条件调用自身就算（必须要有跳出递归的条件，否则死递归）。而在编译器遇到函数调用时候的操作是记录当前上下文和调用位置，函数及参数压栈，运行，返回值到原来调用位置，继续执行。你之所以能够在高级语言中去抽象一些过程和类，就是因为这个人脑可理解的封装调用在计算机上用压栈操作给实现了，使得我们不用管那些细节而只用思考到如何设计递归算法的层面就可以了。

一般来说，因为涉及到压栈出栈，记录上下文，位置等操作，递归的耗时往往要比相同的循环要高，有时是常数级别，有时还是更高复杂度级别的（比如求斐波那契数列的值），且调用层次深，不好调试。故有些编译器会自动把递归等价成循环，可以证明，递归和循环之间是可以相互转换的。只不过把部分编译器的工作在高级语言中自己代替而已。

所以代码建议中，都建议直接写循环而不是递归，但是，递归确是一种更高级的逻辑，有时能够使得代码简洁漂亮。这就看如何把代码可维护调试和效率进行折中了。我们每个人懂得太少，都需要去依赖太多的底层。这些东西是学不完的，一定要有轻重缓急，要出活，那就大胆地相信别人吧！

最后举一个例子，比如遍历一棵树，而树的定义就是一种递归定义的：

有一个根节点，与若干节点有边相连或没有，其中每一个都是一棵树的根节点。

这在结构上和一个包子有好几个包子馅或者没有是一样的。

显然，用递归去遍历就十分舒服：

DFSTree(Tree tree) {
for(int i = 0; i <tree.child_list.size(); i ++) {
cout << tree.child_list[i].node_name << “\n”;
   DFSTree(tree.child_list[i]);
}
}

如果硬要用循环写，其实是很难受的，因为无法确定循环的层数，故只能像递归对应的汇编代码一样，自己模拟出一个栈来，然后自己写入栈和出栈操作，最后栈清空了，循环结束。打着循环的旗号，其实干的是递归的事，这种代码写起来就会比较纠结：

BFSTree(Tree tree) {vector<tree *> tree_list(1), new_tree_list; tree_list[0] = &tree;while(tree_list.size() > 0) {new_tree_list.clear();for (int i = 0;i < tree_list.size(); i ++) {cout << tree_list[i].node_name <<“\n”;  new_tree_list.insert(new_tree_list.end(),tree_list[i].child_list.begin(), tree_list[i].child_list.end());}tree_list = new_tree_list;}}

不过帮编译器做点事情，虽然繁琐，但是有个好处是，对代码细节的把控会更加完善。前提是，这部分你多写出来的逻辑自己也要hold住，否则还不如用人家的东西。毕竟一个编译器是那么多人智慧的结晶，在大部分时候都是比你临时写的东西要优秀的，哪怕并没有为你这个任务来特别优化过。

大家也可以看到，这两个遍历方法恰好递归对应深度优先搜索（DFS），循环对应广度优先搜索（BFS），遍历出来的结果顺序，也恰好也体现了他们的运行逻辑。

好了，关于递归，循环的数理和程序逻辑就先介绍到这里，后面的文章会从魔术艺术的角度对这两个概念进行拓展，看看这些基本的数理逻辑的影子是如何在艺术中体现的。

最后我们会发现，本质上，这类优雅的数学结构下的艺术展现，是符合人的认知规律的，因此才能大一统地总结出如此简单明了的抽象逻辑概念，这大概就是上帝自己的美学追求吧！