Python递归原理与Turtle可视化实战详解

1.学习目标

递归函数是指直接调用自身，或通过一系列语句间接调用自身的函数。在程序设计中，递归具有不可替代的作用，常能优雅地解决复杂问题。尽管递归能高效处理某些难题，但其抽象特性也增加了掌握难度。为深入理解递归背后的逻辑，本节将通过可视化手段展示递归函数的具体执行步骤。

通过本节学习，应掌握以下内容：

深化对递归概念的理解

借助可视化工具解析递归函数内部思想

2.递归的调用

尽管递归能快速解决部分难题，但其抽象性使得理解与掌控变得困难。前文《递归基础》已介绍过递归示例及基本调用过程，但缺乏具体认知。本节将对递归调用机制进行更深入的剖析。

递归函数在执行时，每次递归调用都会在内存中生成一个新的函数副本。当函数调用结束并返回数据后，该副本将从内存中移除。递归方案通常简洁，但跟踪其执行过程却较为复杂。为便于理解，以下通过计算斐波那契数列的简单示例进行说明：

def fibo(n):
    if n == 0:
        return 1
    else:
        return n * fibo(n - 1)
def main():
    number = 4
    result = fibo(number)
    print(result)
if __name__ == "__main__":
    main()

当程序运行至第 10 行时，首次调用 fibo() 函数，系统为 fibo() 创建一条新的活动记录，此时运行时栈上共有 3 条活动记录。随后 Python 解释器跳转至第 2 行，变量 n 指向数字 4，如下图所示。由于 n 不等于 0，程序跳转至第 5 行，该行包含对 fibo() 的函数调用，这将在运行时堆栈上创建另一个活动记录。此过程重复执行，直至 n=0。

需注意，每个递归函数调用都拥有变量 n 的独立副本。活动记录保存了函数作用域内的所有局部变量和参数。每次调用函数时，都会创建新的活动记录，并将局部变量的新副本存储其中。程序运行过程的调用顺序如下图所示：

当函数执行至 n=0 时，fibo() 函数返回其第一个值，将 1 返回至上一层函数调用。如下图所示，系统从运行时堆栈中弹出 n=0 时函数调用的活动记录（图中以灰色表示活动记录的消失）。函数返回后，活动记录所占空间被回收以供后续使用。堆上的阴影对象 0 也因无引用而被垃圾收集器回收。

在首次 fibo() 函数返回后，Python 解释器回到前一个函数调用的第 5 行。该语句同样包含 return 语句，因此函数再次返回至第 5 行，返回值为 1。随后函数再次返回，但此次返回值为 2。遵循上述过程，直至 fibo() 函数返回至 main() 函数的第 8 行，整个过程如下图所示：

最后，程序打印执行结果，在第 9 行之后从 main() 函数返回，并在第 11 行后从 module 返回并终止。从上述示例可见，对 fibo() 函数的每次递归调用都会创建其独立的变量副本。每次调用函数时，局部变量和参数会被复制到相应的活动记录中。当函数调用返回时，对应的活动记录会从运行时堆栈中弹出。这就是递归函数的执行方式。

3.递归可视化

本节将利用 turtle 库进行递归图案绘制，以增强对递归过程的认识。

3.1 turtle 库简介

turtle 库是 Python 的标准库，通常用于绘制图案。使用该库可以创建一只小乌龟 (turtle) 在画布上移动，当小乌龟爬行时会在画布上绘制线条，而当其尾巴抬起时，则不会进行绘制。

接下来，我们将介绍一些基本的 turtle 绘图函数：

• turtle.penup()：抬起 turtle 的尾巴，后续移动不在图上绘制
• turtle.pendown()：放下 turtle 的尾巴，开始爬行，后续会在图上绘制其行动轨迹
• turtle.pensize(width)：用于改变画笔的宽度
• turtle.pencolor(color)：用于改变画笔颜色
• turtle.forward(distance)：向前移动 distance 距离
• turtle.back(distance)：向后移动 distance 距离

3.1 递归绘图

首先，通过创建一个简单的递归函数 draw() 来了解 turtle 库。该递归函数的基本情况为：要画的线长 distance 降为 0；若线长大于 0，则让小乌龟向前绘制 distance 个单位距离，然后左转 30 度；递归情况为：缩短后的距离再次调用 draw() 函数。

# 导入 turtle 库
import turtle
# 创建小乌龟对象
my_turtle = turtle.Turtle()
# 创建用户绘制图案的窗口
window = my_turtle.getscreen()

def draw(turtle, distance):
    if distance > 0:
        # 小乌龟向前绘制 distance 个单位距离
        turtle.forward(distance)
        # 然后左转 30 度
        turtle.left(30)
        draw(turtle, distance-6)
draw(my_turtle, 200)
window.exitonclick()

接下来，我们使用 turtle 模块绘制分形树。分形树与递归有许多共同点，它是数学中的一个概念，无论放大多少倍观察分形图，总能看到相同的基本形状。

如果我们定义树为包含向左生长的子树和向右生长的子树，就可以根据递归的思想得到分形树：

import turtle
def tree(branch, turtle):
    if branch > 5:
        turtle.forward(branch)
        turtle.right(20)
        tree(branch-15, turtle)
        turtle.left(40)
        tree(branch-10, turtle)
        turtle.right(20)
        turtle.backward(branch)
my_turtle = turtle.Turtle()
window = my_turtle.getscreen()
my_turtle.left(90)
my_turtle.up()
my_turtle.backward(300)
my_turtle.down()
tree(110, my_turtle)
window.exitonclick()

到此这篇关于Python数据结构之递归可视化详解的文章就介绍到这了,更多相关Python递归可视化内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！