山东程子太军 SHANDONG UNIVERSITY OF TECHNOLOOY 递归函数的内部执行过程 一个递归函数的调用过程类似于多个函数的嵌套调用， 只不过调用函数和被调用函数是同一个函数。为了保证递 归函数的正确执行，系统需设立一个工作栈。具体地说， 递归调用的内部执行过程如下： (1)运行开始时，首先为递归调用建立一个工作栈，其结 构包括值参、局部变量和返回地址； (2)每次执行递归调用之前，把递归函数的值参和局部变 量的当前值以及调用后的返回地址压栈； (3)每次递归调用结束后，将栈顶元素出栈，使相应的值 参和局部变量恢复为调用前的值，然后转向返回地址指定 的位置继续执行。 2025年4月3日 26
2025年4月3日 26 递归函数的内部执行过程 一个递归函数的调用过程类似于多个函数的嵌套调用， 只不过调用函数和被调用函数是同一个函数。为了保证递 归函数的正确执行，系统需设立一个工作栈。具体地说， 递归调用的内部执行过程如下： （1）运行开始时，首先为递归调用建立一个工作栈，其结 构包括值参、局部变量和返回地址； （2）每次执行递归调用之前，把递归函数的值参和局部变 量的当前值以及调用后的返回地址压栈； （3）每次递归调用结束后，将栈顶元素出栈，使相应的值 参和局部变量恢复为调用前的值，然后转向返回地址指定 的位置继续执行
归东程子末军 SHANDONG UNIVERSITY OF TECINOLOGY 汉诺塔算法在执行过程中，工作栈的变化下图所示，其中栈 元素的结构为（返回地址，值，A值，B值，C值)，返回 地址对应算法中语句的行号。 5,1,A,B,C 7,1,C,A,B 5,2,A,C,B 5,2,A,C,B 5,2,A,C,B 5,2,A,C,B 5,3,A,B,C 5,3,A,B,C 5,3,A,B,C 5,3,A,B,C 5,3,A,B,C (1) (2) (3) (④) (5) 5,1,B,C,A 5,2,A,C,B 7,2,B,A,C 7,2,B,A,C 7,2,B,A,C 5,3,A,B,C 5,3,A,B,C 5,3,A,B,C 5,3,A,B,C 5,3,A,B,C (6) (7) (8) (9) 00 7,1,A,B,C 7,2,B,A,C 7,2,B,A,C 5,3,A,B,C 5,3,A,B,C 5,3,A,B,C 2025而3丽 12 43 Q④ 27
2025年4月3日 27 汉诺塔算法在执行过程中，工作栈的变化下图所示，其中栈 元素的结构为（返回地址，n值，A值，B值，C值），返回 地址对应算法中语句的行号。 ⑾ ⑿ ⒀ ⒁ ⑹ ⑺ ⑻ ⑼ ⑽ ⑴ ⑵ ⑶ ⑷ ⑸ 5, 3, A, B, C 5, 2, A, C, B 5, 3, A, B, C 5, 1, A, B, C 5, 2, A, C, B 5, 3, A, B, C 5, 2, A, C, B 5, 3, A, B, C 7, 1, C, A, B 5, 2, A, C, B 5, 3, A, B, C 5, 2, A, C, B 5, 3, A, B, C 5, 3, A, B, C 7, 2, B, A, C 5, 3, A, B, C 5, 1, B, C, A 7, 2, B, A, C 5, 3, A, B, C 7, 2, B, A, C 5, 3, A, B, C 7, 1, A, B, C 7, 2, B, A, C 5, 3, A, B, C 7, 2, B, A, C 5, 3, A, B, C 5, 3, A, B, C
归东程子太程 SHANDONG UNIVERSITY OF TECINOLOGY 华会清学3会品A空是品 思考题： 如果塔的个数变为a,b,c,d四个，现要将 n个圆盘从a全部移动到d,移动规则不变， 求移动步数最小的方案。 2025年4月3日 28
2025年4月3日 28 思考题： 如果塔的个数变为a,b,c,d四个，现要将 n个圆盘从a全部移动到d，移动规则不变， 求移动步数最小的方案
归本程子末军 SHANDONG UNIVERSITY OF TECINOLOGY 一、 递归的概念 递归小结： ●优，点：结构清晰，可读性强，而且容易用 数学归纳法来证明算法的正确性，因此它 为设计算法、调试程序带来很大方便。 ●缺，点：递归算法的运行效率较低，无论是 耗费的计算时间还是占用的存储空间都比 非递归算法要多。 2025年4月3日 29
2025年4月3日 29 一、递归的概念 递归小结： ⚫优点：结构清晰，可读性强，而且容易用 数学归纳法来证明算法的正确性，因此它 为设计算法、调试程序带来很大方便。 ⚫缺点：递归算法的运行效率较低，无论是 耗费的计算时间还是占用的存储空间都比 非递归算法要多
递归小结 白东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 华绿约条的点会空3会的 解决方法：，在递割归算法中消除递归调用，使其 转化为非递归算法。 上用。一个用户定义的栈来模拟系统的递归调 工作栈，该方通角难，上还递 化爱过徵宁苯球面编革囍南清 归 2只 2、用递推来实现递)归函数。 3、 通过变换能将一些递归转化为尾递归，从而 迭代求出结巢。 后两种方在时空复杂度上均有较大改善 但其适用范围有限。 2025年4月3日 30
2025年4月3日 30 解决方法：在递归算法中消除递归调用，使其 转化为非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调 用工作栈。该方法通用性强，但本质上还是递 归，只不过人工做了本来由编译器做的事情， 优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为尾递归，从而 迭代求出结果。 后两种方法在时空复杂度上均有较大改善， 但其适用范围有限。 递归小结