不会编程的程序员不用懂递归

编程之所以魅力无比，其中一个重要的原因是，一次写入，多次运行，你可能和我一样想象过这样的场景：半躺在椅子上，优雅的点击一个按钮，新的宇宙启动了……

不要觉得这是个幻想，也别只将其停留在幻想之中，这个幻想说明了一个问题，程序可以帮助我们完成更多的事情，而起始点无比的简单，今天我们一起聊聊递归的事情，也许它就是启动宇宙的那个小小按钮

关于递归

一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即可行的。

古典递归函数，是一种定义在自然数集合上的函数，它的未知值往往要通过有限次运算回归到已知值来求出，故称为“递归”。它是古典递归函数论的研究对象

递归的应用场景

递归作为一种算法思想，应用的场景很多，例如著名的汉诺塔问题，即有三个柱子，最左边的上面从小到大串着一定数量的盘子，现在需要将它们移动到最右边的柱子上，原则是移动过程中，以及最终的结果，必须保存小盘子在大盘子上面

还有斐波那契数列，即除了第一个和第二个数为1，其余的数都是前两个数之和，例如 1，1，2，3，5，8……，还有阶乘算法，即，正整数列中，个数为 n 的数相乘，等等举不胜举

在计算机算法中递归更常用，例如二分法查找，快速排序，树的遍历，即对于执行规模不确定，但能拆解为简单步骤的算法，递归几乎都有用武之地，不但可以解决问题，而且语义也更清晰

日常应用中，递归也很普遍，例如遍历文件夹查找文件，处理 XML 文件，再例如 应收账款和收款的匹配，还有最近我 在 TMS 项目遇到的处理箱单层层包裹的关系问题，等等举不胜举

递归与其说是一种编程语言的能力，不如说是一种分析和思考问题的能力，从问题中发现规律，将大问题转换为小问题，知道可以简单计算为止，或者正向思考，前面步骤是后面步骤的计算条件，不断的计算前面的结果，最终得到预订步骤的结果。

递归的特点

既然递归如此好，有没有限制呢？当然有，任何事物都具有两面性，解决问题时要扬长避短

优点

1. 让代码更简洁，逻辑更清晰，代码量更少
2. 为算法设计和代码调试提供便利

注意事项

1. 必须有终止条件，否则将会陷入死循环
2. 递归规模需要有控制，否则会造成程序堆栈溢出，具体受制于操作系统环境，python 默认为 1000 层
3. 构造方法中不能使用递归
4. 递归可以简化程序逻辑，但不能提高运行效率，递归的基础是通过在内存中创建堆栈完成的，如果不加优化，处理过程是非并非的
5. 递归算法的时间复杂度为 O(n3)，即运算时间会以规模的3次幂速度增长，可以这么感受下，假如汉诺塔中，盘子有64层，用现在最先进的计算，所花的时间将远远超过宇宙的年龄

实践

终于到了实践部分了，为您的耐心点赞，我们用递归算法画一棵分形树

分形树就是一棵树的局部形状和整体形状相似，自然界中很常见，例如一片叶子上的形状，和整棵树的形状相似，即整棵树由样式相同的无数个从小到大的形状构成

那么如何用程序画出一个分形树呢？可以先画最小的，然后画次大的，最后组成整个形状，就是今天聊的 递归算法

Turtle 绘图库

既然要画，就需要安装一个画库工具，Python 中有各式各样的绘图包，我们选用 Turtle 库，库如其名，可以将 Turtle 想象成一个小乌龟，逐渐在海滩上移动，画出一个图形来，通过将简单图形组合起来，可以轻松地绘制出精美的形状和图案

安装

> pip install turtle

概念

• 画布: 就是 turtle 为我们展开用于绘图区域，可以设置它的大小和初始位置
• 画笔: 就是用来绘制线条的笔头，可以设置粗细，颜色，方向等属性
• 绘图命令: 用来控制画笔朝向、移动、落笔、起笔等动作的，还有命令是用于做全局设置的，例如清除画布，撤销前一个动作等

示例

有了这些概念，就可以通过代码来设置画布，控制画笔绘制图形了，代码很简单：

from turtle import Turtle
myTurtle = Turtle()
myTurtle.forward(100)

• 先引入构造方法 Turtle
• 创建一个 Turtle 实例，会初始化一个画笔，并且将画笔放置在画布中心位置，方向朝右
• 调用向前移动方法 forward 画一条长度为 100 个像素的直线

绘制分形树

有了绘制工具，就解决了技术问题，现在可以专心思考算法了

问题设定

为了简便，选择最简单的二叉分形树来画，最基本形状是一个二叉树，由树干和左右两个枝叉组成，左右树杈于树干的夹角设置为 20 度，像一个 Y 字

问题分析

• 常规思维：先画根树干，然后分别画两个树杈，每个树杈又是一棵树，接着在各自的树干上再画出两个树杈，如此循环往复，直到画出最小树的两个树杈为止
  
• 递归思维：在画根树干后，假如先画右侧分枝，画完后，这个分枝如果不是最小树的枝，就需要为其画右分支，如此往复，直到画出了最小树的右侧分枝，此时就可以画最小树的左侧分枝了，当画完左侧分枝后，就画完整了一颗最小树，于是可以画比最小数大一级的树的左侧分枝了，如此往复，直到绘制完整棵树

是不是有点绕？下面的图片展示了部分绘制过程，可能更直观：

实现

直接上代码：

from turtle import Turtle
# 分形树递归方法
def fractalTree(branchLen, t):
    if branchLen > 0:
        t.forward(branchLen)
        t.right(20)
        fractalTree(branchLen - 15, t)
        t.left(40)
        fractalTree(branchLen - 15, t)
        t.right(20)
        t.backward(branchLen)
# 初始化画布和画笔
t = Turtle()  # 创建画布实例
t.screen.delay(3)  # 设置绘制显示延迟，以便观察过程
t.pensize(2)  # 设置画笔粗细为 2 个像素
t.color('green')  # 设置画笔颜色为 绿色
t.left(90)  # 向左旋转 90 度，即让画笔朝上
t.up()  # 抬起画笔，即在移动时不会绘制
t.backward(300)  # 相对画笔朝向，向后退 300 个像素
t.down()  # 落下画笔，准备绘制
# 绘制分形树，根树干长度为 105 像素
fractalTree(105, t)
# 获取画布窗口，并设置关闭条件为点击窗口，以便在执行完成后保留绘图窗口
t.getscreen().exitonclick()

上面代码分为三部分，Turtle 引入、分形树方法定义，以及分形树绘制

Turtle 引入不必解释，分形树绘制部分有详细注释，也不必多说，主要分析下分形树方法 fractalTree：

• 首先设置退出条件，即当要绘制的树干长度小于等于 0 时，结束绘制过程，不再继续绘制
• 如果绘制的树干长度大于 0，先向前绘制出树干，注意，画笔方向已经被设置为向上
• 然后将画笔向右调整 20 度，准备绘制右侧树枝
• 右侧树枝应该比树干短一下，这里设置为短 15 个像素（不同的数值画出的树略有不同），由于不知道当前树是否为最小树，所以将画右侧树枝的任务，交给分形树方法，同时设定了根树干长度，即，当前树干长度减去 15 像素
• 如果右侧树枝画完了，向左转 40 度，即 20 度将画笔调整为向上，再转 20 度，就为画左侧树枝的角度
• 同画右侧树枝一样，将当前树干长度减 15 像素，作为左侧树杈长度
• 如果左侧树枝画完后，将画笔向右调整 20 度，即与树干方向一致，然后回退到树干起点

整体上看，过程就是，画树干，然后画右侧分枝，再画左侧分枝，最后回到起点，不过在画两侧分枝时，我们用了递归，让画树的过程得到重复利用，如果顺利，就会看到上面展示的绘制过程，赶紧试试吧

花絮

看似上面过程很顺利，其实不然，我在编写代码时，不断的陷入思维的漏洞，要么是设置错了画笔方向，要么是画笔没有回退到位，等等，乌龙无数（汗！），看下翻车记录：

不过也挺好看的，不是吗

总结

今天通过画一颗分形树，了解了一下递归的概念和应用，整体感觉递归代码短小，但思考过程比正常编程过程要复杂的多，不过这就是编程的魅力，更确切的说是数学的魅力，用简单的符号语言，描绘纷繁复杂的世界…… 最重要的是，Python 支持递归 示例代码中，不仅有分形树方法及翻车代码，还有个彩蛋，欢迎把玩