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

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

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

关于递归

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

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

递归的应用场景

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

汉诺塔

还有斐波那契数列,即除了第一个和第二个数为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 想象成一个小乌龟,逐渐在海滩上移动,画出一个图形来,通过将简单图形组合起来,可以轻松地绘制出精美的形状和图案

安装

1
> pip install turtle

概念

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

示例

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

1
2
3
4
from turtle import Turtle

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

绘制分形树

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

问题设定

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

问题分析

  • 常规思维: 先画根树干,然后分别画两个树杈,每个树杈又是一棵树,接着在各自的树干上再画出两个树杈,如此循环往复,直到画出最小树的两个树杈为止

  • 递归思维: 在画根树干后,假如先画右侧分枝,画完后,这个分枝如果不是最小树的枝,就需要为其画右分支,如此往复,直到画出了最小树的右侧分枝,此时就可以画最小树的左侧分枝了,当画完左侧分枝后,就画完整了一颗最小树,于是可以画比最小数大一级的树的左侧分枝了,如此往复,直到绘制完整棵树

是不是有点绕?下面的图片展示了部分绘制过程,可能更直观: 画图

实现

直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 度,即与树干方向一致,然后回退到树干起点

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

花絮

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

失败案例1

再来一个

失败案例2

不过也挺好看的,不是吗

总结

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

参考

示例代码:https://github.com/JustDoPython/python-examples/tree/master/taiyangxue/recursion

Python Geek Tech wechat
欢迎订阅 Python 技术,这里分享关于 Python 的一切。