2018/05/08 11:18

# python递归函数

## 什么是递归?

``````def recursion(n):  # 定义递归函数
print(n)  # 打印n
recursion(n+1)  # 在函数的运行种调用递归

recursion(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
``````

``````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
``````

• 1.必须要有一个明确的结束条件, 否则就变成死循环导致栈溢出
• 2.每次进入更深一层递归时，问题规模相比上次递归都应有所减少，这句话的以上就是说，每进入一次递归，就会解决一些东西，数据量就会越来越小，最终解决了所有的问题，如果进入一次递归没有解决问题，那么不管递归多少层都没有意义，直到导致栈溢出。
• 3.递归效率比较低，递归层次过多会导致栈溢出，意思是：每当进入一次函数调用，栈就会加一层栈帧，每当函数返回，就减少一层栈帧，由于栈不是无限大小的，所以，递归调用的次数过多，会导致栈溢出。

## 尾递归

``````def story() {
从前有座山，
山上有座庙，
庙里有个老和尚，
一天老和尚对小和尚讲故事：story() // 尾递归，进入下一个函数不再需要上一个函数的环境了，得出结果以后直接返回。
}
def story() {
从前有座山，
山上有座庙，
庙里有个老和尚，
一天老和尚对小和尚讲故事：story()，小和尚听了，找了块豆腐撞死了 // 非尾递归，下一个函数结束以后此函数还有后续，所以必须保存本身的环境以供处理返回值。
}
``````

``````def cal(n):
print(n)
return cal(n+1)  # return代表函数的结束
cal(1)  # 这个会一直打印，直到导致栈溢出
# 调用下一层的同时，自己就退出了
``````

0
0 收藏

0 评论
0 收藏
0