第3章 递归算法.pptx

第3章递归算法2024/9/101主要内容● 递归算法● 递归的复杂度● 问题与子问题● 递归与迭代● 多重递归● 经典递归● 优化递归递归算法是非常最重的算法，是很多算法的基础算法。递归算法不仅能使得代码优美简练，容易理解解决问题的思路或发现数据的内部的逻辑规律，而且具有很好的可读性。和排序算法不同，许多经典的排序算法已经是玲珑剔透、日臻完善，在许多应用中只要选择一种排序算法直接使用即可（见第4章和第12章），而对于递归算法，真正理解递归算法内部运作机制的细节、才能真对实际问题正确的使用递归算法或写出正确的递归算法。

3.1递归算法递归算法是指一个方法在执行过程中又调用了自身、形成了递归调用，这样的方法被称为递归方法或递归算法。2024/9/102?

2024/9/1033.1递归算法递归过程中的压栈、弹栈方法f递归过程是，第k次调用f需要等待第k+1次调用f结束执行过程后才能结束执行过程。那么第R(n)次（最后一次）调用f结束执行过程后，就会依次使得第k次调用结束执行过程。方法被调用时，方法的（入口）地址会被压入栈（栈是一种先进后出的结构）中，称为压栈操作，同时方法的局部变量被分配内存空间。????……调用调用调用调用调用结束?结束?结束?结束结束?图3.1递归执行过程第1次调用第R(n)次调用

2024/9/1043.1递归算法递归过程中的压栈、弹栈方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。递归过程的压栈操作可以让栈的长度不断增加，而弹栈操作会让栈的长度变小，最终使栈的长度为0。…………????第1次弹栈第m次弹栈第k次弹栈第1次压栈第m次压栈第k次压栈

2024/9/1053.1递归算法时间复杂度方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。要针对具体的递归方法，来计算该递归方法的时间复杂度。递归方法是一个递归过程，从递归开始到递归结束，方法被调的总数R(n)是依赖于一个正整数n的函数。那么递归方法中基本操作被执行的总数T(n)就依赖递归的总数R(n)和每次递归时基本操作被执行的总数。

2024/9/1063.1递归算法空间复杂度方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。递归会让栈的长度不断发生变化，如果栈的长度较大可能导致栈溢出，使得进程（运行的程序）被操作系统终止。递归过程的压栈操作增加栈的长度、弹栈操作减小栈的长度。递归过程中可能交替地进行压栈操作和弹栈操作，直至栈的长度为0（见例子2）。计算出递归过程中，某一时刻（某一次递归）栈出现的最大长度和每次递归中方法的局部变量所占的内存空间，即计算出栈最大长度以及局部变量所占的全部内存空间和所依赖的正整数的关系，才可以知道空间复杂度。

2024/9/1073.2线性递归与非线性递归●线性递归线性递归是指，每次递归时，方法调用自身一次。?如果我们忘记了今天是星期几，就需要知道昨天是星期几，如此这般地向前（过去）翻日历（相当于递归里的压栈，导致栈的长度在增加），等到能翻到某个日历页上显示了星期几，就结束翻阅日历（相当于结束压栈），然后再一页一页的撕掉日历（相当于弹栈），日历上神奇地出现了星期数，即方法依次计算出自己的返回值。Week.java例子1Example3_1.java

2024/9/1083.2线性递归与非线性递归●线性递归递归方法f(intn)的递归的总次数：R(n)=n，而每次递归的基本操作只有2个基本操作，因此时间复杂度是O(n)。向下方向的弧箭头表示方法被调用，向上方向的直箭头表示方法调用结束。例子1压栈操作过程中得到的栈的最大长度是R(n)=n，空间复杂度是O(n)。

2024/9/1093.2线性递归与非线性递归●非线性递非线性递归是指，每次递归时方法，调用自身2次或2次以上。?Fibonacci.java例子2Example3_2.java

2024/9/10103.2线性递归与非线性递归●非线性递例子2递归过程中，每次递归时方法调用自身2次，使得每次递归出现了2个递归“分支”，然后选择一个分支，继续递归，直到该分支递归结束，再沿着下一分支继续递归，当2个分支都递归结束，递归过程才结束，而且递归过程交替地进行压栈和弹栈操作，直至栈的长度为0。?

2024/9/10113.3问题与子问题将规模大的问题，使用递归算法逐步分解成规模小的问题，最终解决规模大的问题。一个问题的子问题就是数据规模比此问题的规模更小的问题。当一个问题，可以分解成许多子问题时就可以考虑用递归算法来解决这个问题。

2024/9/10123.3问题与子问题?SumMulti.java例子3Example3_3.java

2024/9/10133.3问题与子问题?Reve