Python科赫曲线

1. 递归

1.1 定义

函数作为一种代码封装， 可以被其他程序调用，当然，也可以被函数内部代码调用。这种函数定义中调用函数自身的方式称为递归。就像一个人站在装满镜子的房间中，看到的影像就是递归的结果。递归在数学和计算机应用上非常强大，能够非常简洁地解决重要问题。

数学上有个经典的递归例子叫阶乘，阶乘通常定义如下:

n!= n(n- 1)(n- 2)…(1)

为了实现这个程序，可以通过一个简单的循环累积去计算阶乘。观察 5! 的计算，如果去掉了 5，那么就剩下计算 4!，推广来看，n!=n(n-1)!。 实际上，这个关系给出了另一种表达阶乘的方式：

当 n = 0 时，n! = 1；否则，n! = n(n - 1)!

这个定义说明 0 的阶乘按定义是 1，其他数字的阶乘定义为这个数字乘以比这个数字小 1 数的阶乘。递归不是循环，因为每次递归都会计算比它更小数的阶乘，直到 0!。0! 是已知的值，被称为递归的基例。当递归到底了，就需要一个能直接算出值的表达式。

阶乘的例子揭示了递归的两个关键特征：

(1) 存在一个或多个基例，基例不需要再次递归，它是确定的表达式。

(2) 所有递归链要以一个或多个基例结尾。

1.2 数学归纳法

数学归纳法和递归都利用了递推原理，本质是相同的。在证明一个与自然数相关的命题 P(n) 时，数学归纳法采用如下步骤。

(1) 证明当 n 取第一个值 n0 时命题成立。

(2) 假设当 nk ( k ≥ 0, k 为自然数 ) 时命题成立，证明当 n=nk+1 时命题也成立。

综合 (1) 和 (2)，对一切自然数 n( n ≥ n0)，命题 P(n) 都成立。

2. 递归的使用方法

2.1 阶乘

以阶乘计算为例，可以把阶乘写成一个单独的函数，则该函数如下所示：

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

num = eval(input("请输入一个整数："))
print(fact(abs(int(num))))

fact() 函数在其定义内部引用了自身，形成了递归过程(如第 5 行)。无限制的递归将耗尽计算资源，因此，需要设计基例使得递归逐层返回。fact() 函数通过 if 语句给出了 n 为 0 时的基例，当 n==0，fact() 函数不再递归， 返回数值 1，如果 n!=0，则通过递归返回 n 与 n-1 阶乘的乘积。

由于负数和小数通过减 1 无法到达递归的基例 (n==0)， 代码第 8 行通过 abs() 和 int() 函数将用户输入转变成非负整数，该程序输出效果如下:

请输入一个整数：5

120

请输入一个整数：6.789

720

递归遵循函数的语义，每次调用都会引起新函数的开始，表示它有本地变量值的副本，包括函数的参数。每次函数调用时，函数参数的副本会临时存储，递归中各函数再运算自己的参数，相互没有影响。当基例结束运算并返回值时，各函数逐层结束运算，向调用者返回计算结果。

使用递归一定要注意基例的构建，否则递归无法返回将会报错。

2.2 字符串反转

对于用户输入的字符串 s，输出反转后的字符串。

解决这个问题的基本思想是把字符串看作一个递归对象。长字符串由较短字符串组成，每个小字符串也是一个对象。假如把一个字符串看成仅由两部分组成：首字符和剩余字符串。如果将剩余字符串与首字符交换，就完成了反转整个字符串，代码如下：

def reverse(s):
    return reverse((s[1:]) + s[0])

观察这个函数的工作过程。s[0] 是首字符，s[1:] 是剩余字符串，将它们反向连接，可以得到反转字符串。执行这个程序，结果如下:

def reverse(s):
    return reverse(s[1:]) + s[0]
reverse("abc")

return reverse(s[1:]) + s[0]
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

这个错误表明系统无法执行 reverse() 函数创建的递归，这是因为 reverse() 函数没有基例，递归层数超过了系统允许的最大递归深度。默认情况下，当递归调用到 1000 层，Python 解释器将终止程序。递归深度是为了防止无限递归错误而设计的，当用户编写的正确递归程序需要超过 1000 层时，可以通过如下代码设定：

import sys
sys.setrecursionlimit(2000)    # 2000 是新的递归层数

reverse() 超过递归深度是因为没有设计基例。字符串反转中的递归调用总是使用比之前更短的字符串，因此，可以把基例设计为字符串的最短形式，即空字符串。

完整代码如下：

def reverse(s):
    if s == "":
        return s
    else:
        return reverse(s[1:]) + s[0]

str = input("请输入一个字符串：")
print(reverse(str))

程序执行结果如下：

请输入一个字符串：Python程序设计
计设序程nohtyP

3. 科赫曲线的绘制

3.1 概要

这是一个采用递归方法绘制科赫曲线的实例，分形几何采用类似递归的核心思想。

自然界有很多图形很规则，符合一定的数学规律， 例如，蜜蜂的蜂窝是天然的等边六角形等。科赫曲线在众多经典数学曲线中非常著名，由瑞典数学家冯。科赫( H-V-Koch )于 1904 年提出，由于其形状类似雪花，也被称为雪花曲线。

科赫曲线的基本概念和绘制方法如下：

正整数 n 代表科赫曲线的阶数，表示生成科赫曲线过程的操作次数。科赫曲线初始化阶数为 0，表示一个长度为 L 的直线。对于直线 L，将其等分为 3 段，中间一段用边长为 L/3 的等边三角形的两个边替代，得到 1 阶科赫曲线，它包含 4 条线段。进一步对每条线段重复同样的操作后得到 2 阶科赫曲线。继续重复同样的操作 n 次可以得到 n 阶科赫曲线，如下图所示：

3.2 绘制科赫曲线

科赫曲线属于分形几何分支，它的绘制过程体现了递归思想，绘制过程代码如下：

import turtle
def koch(size, n):
    if n == 0:
        turtle.fd(size)
    else:
        for angle in [0, 60, -120, 60]:
            turtle.left(angle)
            koch(size / 3, n - 1)
def main():
    turtle.setup(800, 400)
    turtle.speed(0)  # 控制绘制速度
    turtle.penup()
    turtle.goto(-300, -50)
    turtle.pendown()
    turtle.pensize(2)
    koch(600, 6)  # 0阶科赫曲线长度，阶数
    turtle.hideturtle()

main()

程序执行结果如下：

n 阶科赫曲线的绘制相当于在画笔前进方向的 0°、60°、-120° 和 60° 分别绘制 n-1 阶曲线。上述代码中 main() 函数设置了一些初始参数，如果希望控制绘制科赫曲线的速度，可以采用 turtle.speed() 函数增加或减少速度。

3.3 科赫曲线的雪花效果

科赫曲线从一条直线绘制开始，如果从倒置的三角形开始将更有趣。替换前面代码中的 main() 函数，代码如下：

import turtle

def koch(size, n):
    if n == 0:
        turtle.fd(size)
    else:
        for angle in [0, 60, -120, 60]:
            turtle.left(angle)
            koch(size / 3, n - 1)

def main():
    turtle.setup(600, 600)
    turtle.speed(1000)
    turtle.penup()
    turtle.goto(-200, 100)
    turtle.pendown()
    turtle.pensize(2)
    level = 5
    koch(400, level)
    turtle.right(120)
    koch(400, level)
    turtle.right(120)
    koch(400, level)
    turtle.hideturtle()

main()

程序执行结果如下：

3.4 分形几何

分形几何学是数学的一个分支，以不规则几何形态为研究对象。分形以自相似结构为基础，通过无限递归方式展示复杂表面下的内在数学秩序。分形几何不仅展示了数学之美，也揭示了世界的本质，使人们重新审视这个世界：世界是非线性的，分形无处不在。