直接递归函数、尾递归5/23尾算法

思考：如果有头节点会发生什么？ ？ ？ 11/题：X、Y、Z的塔基在X塔基上有n个不同直径的圆盘，从小到大编号为1到n。 要求将 X 塔基上的 n 个圆盘移动到 Z 塔基上。 3、该问题的求解方法是递归的。 3、该题的求解方法是递归移动规则：一次只能移动一个圆盘； 圆盘可插入X、Y、Z任意塔座； 任何时候您都不能将较大的盘子放在较小的盘子上。 12/23 将“大问题”转化为几个“小问题”来解决。 让 Hanoi(n, x, y, z) 表示将 n 个圆盘从 x 通过 y 移动到 z。 13/23fun(1)=15.1.3 递归模型 递归模型是递归算法的抽象，反映了递归问题的递归结构。 比如n!对应的递归模型递归算法如下： 递归出口递归体 一般情况下，递归模型由递归出口和递归体组成。 14/23递归退出决定递归何时结束。 递归体决定了递归求解时的递归关系。 递归退出的一般格式如下：它们都是常量。 一些递归问题可能有多个递归退出。 15/23 递归体的一般格式如下： g 是一个非递归函数 16/23 解决一个大问题并利用变换常数解决几个类似的子问题来变换一个不能或不能的“大问题”很容易解决，直接分解成一个或几个“小问题”来解决；然后进一步将这些“小问题”分解为更小的“小问题”来解决递归思想17/23但是递归分解不是随机分解。递归分解必须确保“大问题”和“小问题”相似，即解决过程和环境相似。

每个“小问题”都可以直接解决（此时分解为递归导出），直到例如国家GDP的统计 国家统计局（GDP） 国家统计局（GDP） 某企业（GDP） 某企业(GDP) 海淀区统计局 (GDP) 海淀区统计局 (GDP) 北京市统计局 (GDP) 北京统计局 (GDP) 上海市统计局 (GDP) 上海市统计局 (GDP) 递归导出大题 18/23 小题问题）分解过程如下： 为了讨论方便，将上面的递归模型简化如下： 19/23 当遇到递归退出时，就发生了“质变”，即原来的递归问题是转化为可以直接解决的问题。 求值过程：这样就计算出了f(s)，因此递归执行过程由分解和求值两部分组成。 20/23求解fun(5)即5！的过程如下：fun(5)递归退出fun(4)fun(3)fun(2)fun(1)=1fun(2)=2fun( 3)=6fun(4)=24fun(5)=12021/23 得到F(6)=8。 递归树在解决复杂的递归问题时需要多次分解和求值。 例如：22/2323/23