Python程序设计基础04_7递归ppt课件.pptx

《Python程序设计基础04_7递归ppt课件.pptx》由会员分享，可在线阅读，更多相关《Python程序设计基础04_7递归ppt课件.pptx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在此输入您的封面副标题Python程序设计基础程序设计基础04_7递归递归杭州师范大学杭州师范大学 虞歌虞歌 第第2页页Python程序设计基础程序设计基础函数函数杭州师范大学杭州师范大学 虞歌虞歌 第第3页页Python程序设计基础程序设计基础函数函数每个每个数的阶乘与比它小数的阶乘与比它小1的数的阶乘之间有如下关系：的数的阶乘之间有如下关系：n!=n(n-1)!，将求，将求n!转换成求转换成求(n-1)!，而，而(n-1)!又可以转换成求又可以转换成求(n-2)!，(n-1)!=(n-1)(n-2)!，重复这个过程，直至，重复这个过程，直至0!=1。0!=1称为称为基本情况基本情况。当当“

2、递推递推”到基本情况时，就可以开始到基本情况时，就可以开始“回归回归”，通过，通过0!求出求出1!，通过，通过1!求求出出2!，通过，通过(n-2)!求出求出(n-1)!，最后通过，最后通过(n-1)!求出求出n!。如果如果某个问题的求解可以转换成规模更小的或者更趋向于求出解的同类子某个问题的求解可以转换成规模更小的或者更趋向于求出解的同类子问题的求解，并且从子问题的解可以构造出原问题的解。这种求解问题的问题的求解，并且从子问题的解可以构造出原问题的解。这种求解问题的思想称为递归思想称为递归。递归由两个过程组成：递推和回归。每一步的递推把问题简化成形式相同、但递归由两个过程组成：递推和回归。每

3、一步的递推把问题简化成形式相同、但较简单一些的情况，直至遇到基本情况较简单一些的情况，直至遇到基本情况。正确正确的递归必须是可终止的，递归至少要有一个基本情况，并且要确保递推过的递归必须是可终止的，递归至少要有一个基本情况，并且要确保递推过程最终会到达基本情况。程最终会到达基本情况。杭州师范大学杭州师范大学 虞歌虞歌 第第4页页Python程序设计基础程序设计基础函数函数杭州师范大学杭州师范大学 虞歌虞歌 第第5页页Python程序设计基础程序设计基础函数函数factorialfactorial函数是递归函数函数是递归函数。杭州师范大学杭州师范大学 虞歌虞歌 第第6页页Python程序设计基础

4、程序设计基础函数函数factorial函数共被调用函数共被调用5次，即次，即factorial(4)、factorial(3)、factorial(2)、factorial(1)、factorial(0)。factorial(4)是是main函数调用的，其余函数调用的，其余4次是在次是在factorial函数中调用的，即递归调用函数中调用的，即递归调用4次次。调用调用factorial函数时函数时，并不是，并不是立即得到立即得到factorial(n)的的值值，递归，递归调用，直到调用，直到factorial(0)时才有时才有确定值确定值，直接，直接返回返回1。factorial(1)的返回值

5、为的返回值为1*factorial(0)，即，即1；factorial(2)返回值为返回值为2*factorial(1)，即，即2；factorial(3)返回返回6，最后，最后factorial(4)返回返回24。杭州师范大学杭州师范大学 虞歌虞歌 第第7页页Python程序设计基础程序设计基础函数函数递归函数递归函数有如下有如下特性：特性：函数函数使用使用if语句处理各种不同情况。语句处理各种不同情况。各种各种不同情况中至少包括一个基本情况，用于结束递归。不同情况中至少包括一个基本情况，用于结束递归。每次每次递归调用都会对原问题进行递推，使其逐步逼近某个基本情况，直至遇到递归调用都会对原问

6、题进行递推，使其逐步逼近某个基本情况，直至遇到该基本情况为止该基本情况为止。使用使用递归求解递归求解问题就是将原问题分解为子问题。如果子问题与原问题是相问题就是将原问题分解为子问题。如果子问题与原问题是相似的，只是规模较小，可以递归使用相同的方法求解子问题。似的，只是规模较小，可以递归使用相同的方法求解子问题。杭州师范大学杭州师范大学 虞歌虞歌 第第8页页Python程序设计基础程序设计基础函数函数猴子猴子吃桃问题。猴子第吃桃问题。猴子第1天摘下若干个桃子天摘下若干个桃子，吃，吃了一半，还不过瘾，又多吃了一半，还不过瘾，又多吃了一个。第了一个。第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以

7、后每天早天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时，就只剩下天早上想再吃时，就只剩下一个桃子了。求第一个桃子了。求第1天共摘了多少个桃子。天共摘了多少个桃子。从第从第10天仅剩一个桃子开始往前推算，第天仅剩一个桃子开始往前推算，第9天的桃子个数为：天的桃子个数为：(第第10天的桃子个天的桃子个数数+1)2，第，第8天的桃子个数为：天的桃子个数为：(第第9天的桃子个数天的桃子个数+1)2，第，第1天的桃天的桃子个数为：子个数为：(第第2天的桃子个数天的桃子个数+1)2。假设第假设第n天的桃子

8、个数为天的桃子个数为peach(n)，第，第n+1天的桃子个数为天的桃子个数为peach(n+1)，得到，得到如下递归关系：如下递归关系：杭州师范大学杭州师范大学 虞歌虞歌 第第9页页Python程序设计基础程序设计基础函数函数peachpeach函数是递归函数函数是递归函数。杭州师范大学杭州师范大学 虞歌虞歌 第第10页页Python程序设计基础程序设计基础函数函数用用递归求递归求xn，其中，其中n为整数。为整数。当当n0时，可以得到如下递归关系：时，可以得到如下递归关系：当当n0，这样也可以利用上面的递归关系。，这样也可以利用上面的递归关系。杭州师范大学杭州师范大学 虞歌虞歌 第第11页页

9、Python程序设计基础程序设计基础函数函数powerHelperpowerHelper函数是递归函数函数是递归函数。powerHelperpowerHelper函数是为了实现函数是为了实现powerpower函数而定义的辅助函数函数而定义的辅助函数。powerpower函数只是根据不同情况确定如何使用函数只是根据不同情况确定如何使用powerHelperpowerHelper函数。函数。杭州师范大学杭州师范大学 虞歌虞歌 第第12页页Python程序设计基础程序设计基础函数函数任何任何用递归求解的问题，一般都同样能用循环来求解。用递归求解的问题，一般都同样能用循环来求解。递归有额外开销。递归

10、有额外开销。对于对于某些问题，使用递归能得到一个清晰、简洁的解决方案，而使用其他方法求某些问题，使用递归能得到一个清晰、简洁的解决方案，而使用其他方法求解则会很困难。解则会很困难。使用使用递归还是循环，取决于要求解问题的本质。两种方法，哪种能设计出更递归还是循环，取决于要求解问题的本质。两种方法，哪种能设计出更自然地反映问题本质的直观解决方案，就用哪种方法自然地反映问题本质的直观解决方案，就用哪种方法。如果可以很直接地设计出循环方案，那么就用循环，通常比递归方案效率要高如果可以很直接地设计出循环方案，那么就用循环，通常比递归方案效率要高。如果如果在意程序的性能，应该尽量避免使用递归。在意程序的

11、性能，应该尽量避免使用递归。杭州师范大学杭州师范大学 虞歌虞歌 第第13页页Python程序设计基础程序设计基础函数函数编写程序，求斐波纳契（编写程序，求斐波纳契（Fibonacci）数列的第）数列的第n项的值。项的值。Fibonacci 数列: 0 1 1 2 3 5 8 13 21 34 55 89 下标: 0 1 2 3 4 5 6 7 8 9 10 11 数列以数列以0和和1开始，随后的每个数是数列中它前面两个数之和。开始，随后的每个数是数列中它前面两个数之和。fib(3) = fib(2) + fib(1) = (fib(1) + fib(0) + fib(1) = (1 + 0)

12、+ fib(1) = 1 + fib(1) = 1 + 1 = 2杭州师范大学杭州师范大学 虞歌虞歌 第第14页页Python程序设计基础程序设计基础函数函数fib函数函数是递归函数。是递归函数。运行时间运行时间（化为（化为毫秒并取整），毫秒并取整），不同不同的计算机系统有的计算机系统有差异差异。time模块中的模块中的time方法返回以毫秒为精度的从方法返回以毫秒为精度的从1970年年1月月1日日00:00:00开始到当前的格林威治时间（秒数）开始到当前的格林威治时间（秒数）。杭州师范大学杭州师范大学 虞歌虞歌 第第15页页Python程序设计基础程序设计基础函数函数fib函数许多函数许多递

13、归调用是重复递归调用是重复的的。fib(2)调用了调用了2次，次，fib(1)调用了调用了3次，次，fib(0)调用了调用了2次。次。n越大，递归调用的次数会大大增加。一般来说，计算越大，递归调用的次数会大大增加。一般来说，计算fib(n)需要进行的递归调用次数是计算需要进行的递归调用次数是计算fib(n-1)所需要递归调用次数的所需要递归调用次数的2倍。倍。n增加增加1，fib(n)的计算时间将为原来的的计算时间将为原来的1.6倍左右。倍左右。杭州师范大学杭州师范大学 虞歌虞歌 第第16页页Python程序设计基础程序设计基础函数函数fib函数的递归实现效率很差，使用循环来实现函数的递归实现

14、效率很差，使用循环来实现fib函数是更好的选择。斐波函数是更好的选择。斐波纳契数列以纳契数列以0和和1开始，随后每个数都是数列中它前面两个数之和。因此，可开始，随后每个数都是数列中它前面两个数之和。因此，可以得到如下关系：以得到如下关系：（1）f0和和f1已知；已知；（2）由）由f0和和f1可以计算出可以计算出f2；（3）可以从）可以从f0和和f1出发，向前逐个推算，直至算出所需的出发，向前逐个推算，直至算出所需的fn为止。为止。杭州师范大学杭州师范大学 虞歌虞歌 第第17页页Python程序设计基础程序设计基础函数函数fib函数函数是非递归函数。是非递归函数。运行时间运行时间（化为（化为毫秒

15、并取整），毫秒并取整），不同不同的计算机系统有的计算机系统有差异差异。在在计算时间上，新的计算时间上，新的fib函数有很大优越性，函数的主体就是一函数有很大优越性，函数的主体就是一个循环，所需时间由循环次数确定，而循环体的执行次数等于个循环，所需时间由循环次数确定，而循环体的执行次数等于参数参数n的大小。的大小。杭州师范大学杭州师范大学 虞歌虞歌 第第18页页Python程序设计基础程序设计基础函数函数若若从递归调用返回时没有待处理操作要完成，那么这个递归函数就是尾递归从递归调用返回时没有待处理操作要完成，那么这个递归函数就是尾递归函数。函数。递归函数递归函数A是尾递归函数：是尾递归函数： 递

16、归函数递归函数A 递归调用函数递归调用函数A因为每次递归调用函数因为每次递归调用函数A返回时没有待处理操作要完成。返回时没有待处理操作要完成。递归函数递归函数B不是尾递归函数不是尾递归函数：递归函数递归函数B 递归调用函数递归调用函数B 每次每次递归调用函数递归调用函数B返回时都有待处理操作要返回时都有待处理操作要完成。完成。杭州师范大学杭州师范大学 虞歌虞歌 第第19页页Python程序设计基础程序设计基础函数函数尾递归尾递归有助于减少占用内存大小。当最后一个递归调用结束时，递归函数也有助于减少占用内存大小。当最后一个递归调用结束时，递归函数也结束了。无须将中间调用过程存储在内存中。结束了。无须将中间调用过程存储在内存中。使用使用辅助参数将非尾递归函数转换为尾递归函数。辅助参数用来存储结果。辅助参数将非尾递归函数转换为尾递归函数。辅助参数用来存储结果。 factorial函数调用了函数调用了factorial_helper辅助函数辅助函数。factorial_helper辅助函数带有辅助参数辅助函数带有辅助参数result，它存储了它存储了n阶乘的结果阶乘的结果。递归递归调用调用factorial_helper辅助函数，在递归调辅助函数，在递归调用返回后，没有待处理操作。用返回后，没有待处理操作。