4.2递归调用的实现与分形图（Python进阶-数据结构与算法）课件

递归调用的实现 数据结构与算法（Python版） ❖ 当一个函数被调用的时候 ， 系统会把调用 时的现场数据压入到系统调用栈 每次调用，压入栈的现场数据称为栈帧 当函数返回时，要从调用栈的栈顶取得返回地址 数据结构与算法（Python版） ,恢复现场，弹出栈帧，按地址返回。 栈帧 返回次序 递归调用的实现 0 调用次序 入栈 入栈 入栈 入栈 ❖ 在调试递归算法程序的时候经常会碰到这 样的错误： RecursionError 递归的层数太多，系统调用栈容量有限 数据结构与算法（Python版） Python中的递归深度限制 0 ❖ 这时候要检查程序中是否忘记设置基本结 束条件 ， 导致无限递归 或者向基本结束条件演进太慢，导致递归层数太 多，调用栈溢出 数据结构与算法（Python版） Python中的递归深度限制 0 ❖ 在Python内置的sys模块可以获取和调整 最大递归深度 数据结构与算法（Python版） Python中的递归深度限制 0 ❖ 前目的地.Predestination.2014 自身产生自身的闭环烧脑递归 ❖ 恐怖游轮.Triangle.2009 调用栈栈帧大混合，如何才能终结一切，返回主 数据结构与算法（Python版） 递归的故事 0 函数？ ❖ 前面的种种递归算法展现了其简单而强大 的一面 ， 但还是难有个直观的概念 ❖ 下面我们通过递归作图来展现递归调用的 视觉影像 数据结构与算法（Python版） 递归可视化：图示 0 ❖ Python的海龟作图系统turtle module Python内置，随时可用，以LOGO语言的创意为 基础 其意象为模拟海龟在沙滩上爬行而留下的足迹 爬行： forward(n); backward(n) 转向： left(a); right(a) 抬笔放笔： penup(); pendown() 笔属性： pensize(s); pencolor(c) 数据结构与算法（Python版） 递归可视化：图示 0 数据结构与算法（Python版） 递归可视化：图示 0 数据结构与算法（Python版） 0 海龟作图 数据结构与算法（Python版） 0 海龟作图 数据结构与算法（Python版） 一个递归作图的例子：螺旋 最小规模， 0直接退出 减小规模，边长减5 0 调用自身 ❖ 分形Fractal ， 是1975年由Mandelbrot 开创的新学科 “一个粗糙或零碎的几何形状，可以分成数个部 分，且每一部分都（至少近似地）是整体缩小后 的形状”， 即具有自相似的性质。 数据结构与算法（Python版） 分形树：自相似递归图形 0 ❖ 自然界中能找到众多具有分形性质的物体 海岸线、山脉、闪电、云朵、雪花、树 http://paulbourke.net/fractals/googlee arth/ http://recursivedrawing.com/ 数据结构与算法（Python版） 分形树：自相似递归图形 0 数据结构与算法（Python版） 自然界不是平滑的 0 ❖ 自然现象中所具备的分形特性 ， 使得计算 机可以通过分形算法生成非常逼真的自然 场景 ❖ 分形是在不同尺度上都具有相似性的事物 我们能看出一棵树的每个分叉和每条树枝，实际 上都具有整棵树的外形特征（也是逐步分叉的） 数据结构与算法（Python版） 分形树：自相似递归图形 0 = + ❖ 这样 ， 我们可以把树分解为三个部分： 树 干、 左边的小树、 右边的小树 分解后，正好符合递归的定义： 对自身的调用 数据结构与算法（Python版） 分形树：自相似递归图形 二叉树 树干 倾斜的右小树 倾斜的左小树 0 + 数据结构与算法（Python版） 分形树：代码 0 $$