C语言程序设计【共享精品-ppt】.ppt

将上图改为下图 1 ) 假 真 fact(3) 真 假 3==1 调用 fact( 2 真 假 2==1 1==1 f act(2)=2*fact(1) 返回 f act(3)=3*fact(2) 返回 调用 fact( ) fact(1) =1 返回 第六讲 递归及其实现 在这个图中“内层”与“外层”有着相同的结构。它们之间“你中有我，我中有你”，呈现相互依存的关系。 为了进一步讲清递归的概念，将递归与递推做一比较。仍以求阶乘为例。 递推是从已知的初始条件出发，逐次去求所需要的阶乘值。 如求3！ 初始条件 fact(1) = 1 fact(2) = 2*fact(1) = 2 fact(3) = 3*fact(2) = 6 第六讲 递归及其实现 这相当于从菜心“推到”外层。而递归算法的出发点不放在 初始条件上，而放在求解的目标上，从所求的未知项出发逐 次调用本身的求解过程，直到递归的边界（即初始条件）。 就本例而言，读者会认为递归算法可能是多余的，费力而不 讨好。但许多实际问题不可能或不容易找到显而易见的递推 关系，这时递归算法就表现出了明显的优越性。 下面我们将会看到，递归算法比较符合人的思维方式，逻 辑性强，可将问题描述得简单扼要，具有良好的可读性，易 于理解，许多看来相当复杂，或难以下手的问题，如果能够 使用递归算法就会使问题变得易于处理。 第六讲 递归及其实现 故事：相传在古代印度的Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为5800亿年。 C A B 第六讲 递归及其实现 第四讲 数组 【实例】将几个数从大到小排序并输出，冒泡排序法 i=1 i=2 i=3 i=4 i=5 i=6 a[1] a[2] a[3] a[4] a[5] a[6] 初始值 1 8 3 2 4 9 比较1和8,调换 1 8 3 2 4 9 比较1和3,调换 8 1 3 2 4 9 比较1和2,调换 8 3 1 2 4 9 比较1和4,调换 8 3 2 1 4 9 比较1和4,调换 8 3 2 4 1 9 1到达位置 8 3 2 4 9 1 比较8和3,不动 8 3 2 4 9 1 比较3和2,不动 8 3 2 4 9 1 比较2和4,调换 8 3 2 4 9 1 比较2和9,调换 8 3 4 2 9 1 2到达位置 8 3 4 9 2 1 i=1 i=2 i=3 i=4 i=5 i=6 a[1] a[2] a[3] a[4] a[5] a[6] 中间值 8