20210104 递归

5.4.递归 
在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 
1     def calc(n) : 
2          print(n) 
3          if int(n/2) ==0: 
4                return n 
5           return calc(int(n/2) ) 
6 
7     calc(10) 
8 
9     输出: 
10     10 
11     5 
12     2 
13     1 

递归特性: 
1.必须有一个明确的结束条件 
2.每次进入更深一层递归时,问题规模相比上次递归都应有所减少 
3.递归效率不高, 递归层次过多会导致栈溢出(在计算机中, 函数调用是通过栈(stack) 这种数据结构实现 
的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限 
的,所以,递归调用的次数过多,会导致栈溢出) 

1-1
def calc(n):
    print(n)
    return calc(n/2)
# 返回的时候,调用自己,自己又执行了,如果 return 的是 n; 就会变成死循环
# 就像贪吃蛇一样,我吃我自己

1-1-1
def calc(n):
    print(n)
    return calc(n)
calc(10)
--->
RecursionError: maximum recursion depth exceeded while calling a Python object

1-1-2
def calc(n):
    print(n)
    return calc(n+1)
calc(0)
--->
从结果来看,最大的递归数是 999;这是程序的保护机制
比如两个镜子对着照,进入无限循环,外面的函数还没有结束,导致内存很快耗光
所以,递归的第一个特性就是必须有一个明确的结束条件 

2-1
def calc(n):
    print(n)
    if n/2 > 0:
        return calc(n/2)

calc(10)
# 为什么无法结束?因为有小数,所以永远无法结束,需要将它变为整数

2-1-1
def calc(n):
    print(n)
    if int(n/2) > 0:
        return calc(int(n/2))

calc(10)
--->
10
5
2
1

2-1-2
def calc(n):
    print(n)
    if int(n/2) > 0:
        return calc(int(n/2))
    print("-->",n)

calc(10)
--->
10
5
2
1
--> 1

做递归,最好的办法就是加断点调试
上一篇:3-6python语法基础-函数-匿名函数


下一篇:20210526模拟赛总结