什么是递归函数

• 函数定义中调用函数自身的方式称为递归（简单说就是自己调用自己）
  举个简单例子就是：函数f(x)-----f(f(x)) 既是一个递归调用。

每次函数调用时，函数参数会临时存储，相互没有影响；达到终止条件时，各函数逐层结束运算，返回计算结果；要注意终止条件的构建，否则递归无法正常返回结果。

分形树

分形几何学的基本思想：客观事物具有自相似性的层次结构，局部和整体在形态，功能，信息，时间，空间等方面具有统计意义上的相似性，称为自相似性，自相似性是指局部是整体成比例缩小的性质。

下图就是一个分形树，我们将要用python实现它。
在此python中 turtle 用法不再详细介绍 ，具体 turtle 的中方法可参考官网。https://docs.python.org/3/library/turtle.html

分析：

我们先来看一个简单的分形树：

根据分形几何学的理论，图中蓝色框出的部分具有相同的图像特征，只是大小比例不一样。我们从起点开始：
步骤一：向前走X距离
到达岔路口后有两个选择：向左 or 向右。要想画出这个 “Y” 的这个基本图案，其实两步都得走，只是先是选择走左还是走右的问题。
步骤二：假设我们选择向左走
做出选择后，其实我们就又类似回到了起点，执行步骤一：向前走X距离；然后再选择向左还是向右，假如树的层数有很多，我们就进入了一个循环中（一直执行步骤一，步骤二）。

以一层数为例，我们来走一下步骤：

1.起点开始，向前走X距离
2.做出选择，假设我们先向右走
3.先前（X-1）的距离
4.满足终止条件，退回到3的起点（至此右边路走完）
5.向左走，向前走（X-1）的距离
6.满足终止条件，退回到5的起点（至此左边路走完）
7.退回到1的起点。
虽然只有一层，但是我们仔细回看步骤，其实当中已经用到了两层函数（即一次递归）
我们可以定义这样一个函数：F（x，y）,上面 就相当于F（F(x,y）,F(x,y)）.可以理解为数学里的嵌套函数，只不过嵌套的还是自己本身。
上面的函数即为：
1.向前走X
2.做选择
3.判断下一步要走的步长（X-1）是否满足条件，若满足，则又重复（1-3）的步骤，若不满足，退出本层函数（特别强调是退出本层函数，回到上一层继续往下执行）很多人在此不是特别理解，还请多想想。

想清楚后我们来绘制开头的那个分形树：

算法流程：

1.树干初始长度为50，宽度为5（即从起点开始第一步的步长）
2.每次绘制完树枝时，画笔右转20度
3.绘制下一段树枝时，长度减少10，宽度*0.8，重复2-3操作直到终止
4.终止条件：树枝长度小于5，此时为顶端树枝
5.达到终止条件后，画笔左转40度，以当前长度减少15，绘制树枝
6.右转20度，回到原方向，退回上一个节点，直到操作完成
详细代码如下：

import turtle


def pen_fractal_branch(branch_length, branch_width):
    """
        绘制分形树
        branch_length:步长即一段树枝的长度
        branch_width：线宽
    """
    # 终止条件（不能让树无限长下去）
    if branch_length > 5:

        # 绘制右侧树枝
        turtle.color('brown')#设置树的颜色为棕色
        turtle.pensize(branch_width)#设置笔的线宽
        turtle.forward(branch_length)#设置步长
        print('forward：{}'.format(branch_length))
        turtle.right(20)#右转20度
        print('right:20')
        #做完选择之后，又相当于回到有一个起点，
        #开始又一次执行  1.向前，2.做选择（即调用自己）
        pen_fractal_branch(branch_length - 10, branch_width * 0.8)

        #每次调用自己都会不断地进入一层又一层的自己，不断的执行1.前行2.向右。直到最后一层满足终止条件，然后回到上一层，然后再到上一层满足终止条件，再回到上上层，依次类推。
        # 绘制左侧树枝
        turtle.left(40)
        print('left:40')
		# 绘制左侧和右侧一样，执行两个步骤：1.向前，2.选择。（即调用自己）
        pen_fractal_branch(branch_length - 10, branch_width * 0.8)

        # 返回之前的节点
        turtle.right(20)
        print('right:20')
		#改变树枝末梢的颜色为绿色
        if branch_length < 15:
            turtle.color('green')
        else:
            turtle.color('brown')
        turtle.pensize(branch_width)
        turtle.backward(branch_length)


def main():
    """
    主函数
    """
    # 改变落笔的初始位置
    turtle.bgcolor('black')
    turtle.left(90)
    turtle.penup()
    turtle.backward(250)
    turtle.pendown()
    
	#画笔的初始步长和线宽
    pen_fractal_branch(100, 5)
    turtle.exitonclick()


if __name__ == '__main__':
    main()

运行结果如下：

总结一下就是，一层一层的进入，直到满足终止条件，然后再一层一层的退出。

附录：增强版分形树

代码如下：

import turtle


def pen_floor(grass_number, grass_interval):
    """
    绘制地面
    grass_number:种草的数量
    grass_interval:种草的间隔
    """
    # 绘制中间的大树
    pen_fractal_branch(100, 5, 11, 4)
    # 计数器
    count = 0
    while count < grass_number:
        turtle.right(90 * pow(-1, count))
        turtle.color('#8B4513')
        turtle.pensize(2)
        turtle.speed('fastest')
        turtle.forward(grass_interval * (count + 1))
        turtle.left(90 * pow(-1, count))
        count += 1
        pen_fractal_branch(15, 2, 7, 4)


def pen_fractal_branch(branch_length, branch_width, layers_num, green_leaf_layer_num):
    """
        绘制分形树
        branch_length:步长即一段树枝的长度
        branch_width：线宽
        layers_num:树的层数
        green_leaf_layer_num:末端树叶的层数
    """
    # 终止条件（不能让树无限长下去）
    if layers_num > 0:

        # 绘制右侧树枝
        turtle.color('brown')
        turtle.speed('fastest')
        turtle.pensize(branch_width)
        turtle.forward(branch_length)
        print('forward：{}'.format(branch_length))
        turtle.right(20)
        print('right:20')

        pen_fractal_branch(branch_length * 0.8, branch_width * 0.8, layers_num - 1, green_leaf_layer_num)

        # 绘制左侧树枝
        turtle.left(40)
        print('left:40')

        pen_fractal_branch(branch_length * 0.8, branch_width * 0.8, layers_num - 1, green_leaf_layer_num)

        # 返回之前的节点
        turtle.right(20)
        print('right:20')

        if layers_num <= green_leaf_layer_num:
            turtle.color('green')
        else:
            turtle.color('brown')
        turtle.pensize(branch_width)
        turtle.backward(branch_length)


def main():
    """
    主函数
    """
    # 改变落笔的初始位置
    turtle.bgcolor('black')
    turtle.left(90)
    turtle.penup()
    turtle.backward(250)
    turtle.pendown()
    # 设置画笔速度
    turtle.speed('fastest')
    # 画地面
    pen_floor(30, 25)
    turtle.exitonclick()


if __name__ == '__main__':
    main()