Python递归函数详细介绍
发布时间:2021-11-12 16:02:19 所属栏目:教程 来源:互联网
导读:什么是递归? 递归,就是在函数运行中自己调用自己 代码示例: def recursion(n): # 定义递归函数 print(n) # 打印n recursion(n+1) # 在函数的运行种调用递归 recursion(1) # 调用函数 这个函数在不断的自己调用自己,每次调用n+1,看下运行结果: 1 2 ..... 998T
什么是递归? 递归,就是在函数运行中自己调用自己 代码示例: def recursion(n): # 定义递归函数 print(n) # 打印n recursion(n+1) # 在函数的运行种调用递归 recursion(1) # 调用函数 这个函数在不断的自己调用自己,每次调用n+1,看下运行结果: 1 2 ..... 998Traceback (most recent call last): File "D:/py_study/day08-函数/Python递归函数md/01-什么是递归.py", line 11, in <module> recursion(1) File "D:/py_study/day08-函数/python递归函数md/01-什么是递归.py", line 9, in recursion recursion(n+1) File "D:/py_study/day08-函数/python递归函数md/01-什么是递归.py", line 9, in recursion recursion(n+1) File "D:/py_study/day08-函数/python递归函数md/01-什么是递归.py", line 9, in recursion recursion(n+1) [Previous line repeated 993 more times] File "D:/py_study/day08-函数/python递归函数md/01-什么是递归.py", line 8, in recursion print(n) RecursionError: maximum recursion depth exceeded while calling a Python object Process finished with exit code 1 可为什么执行了900多次就报错了呢?还说超过了最大递归深度限制,为什么要限制呢? 通俗来讲,是因为每个函数在调用自己的时候,还没有退出,占内存,多了肯定会导致内存崩溃. 本质上来将,在计算机中,函数调用是通过栈(stack)这样数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会少一层栈帧.由于栈的大小不是无限的,所以,递归调用次数多了,会导致栈溢出. 我们还可以修改递归深度,代码如下: import sys sys.setrecursionlimit(1500) # 修改递归调用深度 def cacl(n): print(n) cacl(n+1) cacl(1) 运行结果如下: 1 2 ...... 1498Traceback (most recent call last): File "D:/py_study/day08-函数/python递归函数md/02-修改递归深度.py", line 11, in cacl cacl(n+1) File "D:/py_study/day08-函数/python递归函数md/02-修改递归深度.py", line 11, in cacl cacl(n+1) File "D:/py_study/day08-函数/python递归函数md/02-修改递归深度.py", line 11, in cacl cacl(n+1) [Previous line repeated 995 more times] File "D:/py_study/day08-函数/python递归函数md/02-修改递归深度.py", line 10, in cacl print(n) RecursionError: maximum recursion depth exceeded while calling a Python object 让我们以最经典的例子说明递归 # 计算n! # 相信很多人都学过阶乘,比如5! = 5*4*3*2*1 n! = n*(n-1)*(n-2)*...*1,那么在递归中该如何实现呢? # 1.打好函数的框架 def factorial(n): # 定义一个计算阶乘的函数 pass # 不做任何操作 factorial(3) # 调用 # 2.考虑两种情况,如果n=1,那么1的阶乘就是1了,如果这个传递的参数大于1,那么就需要计算继承了. def factorial(n): if n == 1: # 判断如果传递的参数是1的情况 return 1 # 返回1,return代表程序的终止 res = factorial(1) # res变量来接受函数的返回值 print(res) # 打印 2.1如果传递的参数不是1,怎么做? def factorial(n): if n == 1: return 1 else: # 5*4! = 5*4*3! = 5*4*3*2! return n * factorial(n-1) # 传递的参数是n,那么再次调用factorial(n-1) res = factorial(1) print(res) 举例2: # 让10不断除以2,直到0为止。 int(10/2) = 5 int(5/2) = 2 int(2/2) = 1 int(1/2) = 0 # 1.同样第一步先打框架 def cacl(n): # 定义函数 pass cacl(10) # 2.那么我们想从10开始打印然后一直到0,怎么做? def cacl(n): # 定义函数 print(n) cacl(10) # 3.已经把打印的值传递进去了,那么就是在里面操作了 def cacl(n): # 定义函数 print(n) # 打印传递进去的值 v = int(n /2) # n/2 if v>0: # 如果v还大于0 cacl(v) # 递归,把v传递进去 print(n) # 打印v,因为已经调用递归了,所以此时的n是v cacl(10) 运行结果如下: 10 5 2 1 1 2 5 10 怎么输出会是这样呢?我刚刚说过,什么是递归?递归就是在一个函数的内部调用函数本身,我们打个比方,递归一共有3层,那么第二层就是调用第一层的结果,第三层又去调用第二层的结果,所以!当上面这个程序运行时,第一次打印的是10,然后除上2,等于是5,再继续除,一直到了1,然后1/2是等于0的,此时就没有调用了递归,但是我还在调用上一层函数,就需要把这个数给返回出来,所以就变成后来的1,2,5,10了。 递归特性 •1.必须要有一个明确的结束条件, 否则就变成死循环导致栈溢出 •2.每次进入更深一层递归时,问题规模相比上次递归都应有所减少,这句话的以上就是说,每进入一次递归,就会解决一些东西,数据量就会越来越小,最终解决了所有的问题,如果进入一次递归没有解决问题,那么不管递归多少层都没有意义,直到导致栈溢出。 •3.递归效率比较低,递归层次过多会导致栈溢出,意思是:每当进入一次函数调用,栈就会加一层栈帧,每当函数返回,就减少一层栈帧,由于栈不是无限大小的,所以,递归调用的次数过多,会导致栈溢出。 那么有没有优化方式呢?肯定是有的 尾递归 我在知乎上找了一个特别有意思的例子来说明下什么是尾递归: def story() { 从前有座山, 山上有座庙, 庙里有个老和尚, 一天老和尚对小和尚讲故事:story() // 尾递归,进入下一个函数不再需要上一个函数的环境了,得出结果以后直接返回。 } def story() { 从前有座山, 山上有座庙, 庙里有个老和尚, 一天老和尚对小和尚讲故事:story(),小和尚听了,找了块豆腐撞死了 // 非尾递归,下一个函数结束以后此函数还有后续,所以必须保存本身的环境以供处理返回值。 } 尾递归,进入下一个函数不再需要上一个函数的环境了,得出结果以后直接返回。 def cal(n): print(n) return cal(n+1) # return代表函数的结束 cal(1) # 这个会一直打印,直到导致栈溢出 # 调用下一层的同时,自己就退出了 (编辑:宁德站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |