75递归
递归的核心: 递进的时候能够达到一个结果,问题规模越来越小(不一定要真正的达到); 设置一个条件,能够让最后一次函数调用结束;
递归代码(递归更多的是一种思想,用来解决某种问题)
递归是函数调用函数本身,然后有结束条件
一、什么是函数递归
函数的嵌套调用是：函数嵌套函数。函数的递归调用：它是一种特殊的嵌套调用，但是它在调用一个函数的过程中，又直接或者间接的调用了它自身。
def foo():
print ('from foo')
foo()
foo()
#这个会死循环
如果递归不断地调用函数自身，那么这个递归函数将会进入一个死循环，因此我们应该给递归函数一个明确的结束条件。
1.1直接调用
直接调用是指：直接在函数内部调用函数自身。
import sys
print(f'最大递归层数：{sys.getrecursionlimit()}')
#输出：
最大递归层数：1000
# 在python3中最大递归层数是1000层
import sys
sys.setrecursionlimit(10000)# 可以修改递归层数
def foo(n):
print('from foo',n)
foo(n+1)
foo(0)
1.2间接调用
间接调用指的是：不在原函数体内调用函数自身，而且是通过其他的方法间接调用函数自身。
def bar():
print('from bar')
foo()
def foo():
print('from foo')
bar()
bar()
递归必须要又俩个明确的阶段
- 递推：一层一层递归调用下去，进入下一层递归的问题规模都将会减小。
- 回溯：递归必须要有一个明确的结束条件，在满足该条件开始一层一层回溯。递归的精髓在于通过不断的重复逼近一个最终的结果。
line = [1 ,2,3,4,5,6]
def howmanyin(lst):
if lst[1:]:
print("hello")
return 1+howmanyin(lst[1:])
else:
print('just me')
return 1
howmanyin(line)
#输出：
hello
hello
hello
hello
hello
just me
def age(n):
if n==1:
return 26
res = age(n-1)+2
return res
print(age(5))
#输出：
34
# 求年龄
# 16/18/20/22/24
# 我知道第一个人的年龄16,我要求出5个人后的年龄-->26
age = 16
# 这就叫递归,有空的去看看 汉诺塔 # age_func(5) = age_func(4) = age_func(3) = age_func(2) = age_func(1) = age_func(0) =26
def age_func(x): # x的规模在减小 # x = 5 # x =4 # x =3 # x =2 # x = 1 # x = 0
global age
if x == 0:
return age # 终止函数,age=26,这是age_func(0)
# age = 18 # age = 20 # age 22 # age = 24 # age = 26
return age_func(x - 1) + 2 # age_func(4) # age_func(3) # age_func(2) # age_func(1) # age_func(0)
res = age_func(5)
print(res) # 26
'''
age_func(5) --> age = 18 --> return age_func(4) # return 26
age_func(4) --> age = 20 --> return age_func(3)
age_func(3) --> age = 22 --> return age_func(2)
age_func(2) --> age = 24 --> return age_func(1) == return age_func(0) == return age == return 26
age_func(1) --> age = 26 --> return age_func(0) == return age == return 26
return age # age = 26
'''
'''
age_func(5) --> return age_func(4)+2 == 24+2 =26
age_func(4) --> return age_func(3)+2 == 22+2 = 24
age_func(3) --> return age_func(2)+2 == 20+2 = 22
age_func(2) --> return age_func(1)+2 == 18+2 = 20
age_func(1) --> return age_func(0)+2 == 16+2= 18
'''
def func(n):
age = 16
age = age + 2 * n
return age
res = func(10)
print(res)
为什么要用递归
递归的本质就是干重复的活，但是仅仅是普通的重复，我们使用while循环就可以了。
lis = [1,[2,[3,[4,[5,[6,]]]]]]
def tell(lis):
for i in lis:
if type(i) is list:
tell(i)
else:
print(i)
tell(lis)
#输出：
1
2
3
4
5
6
三、如何用递归
3.1 二分法的应用
有一个从小到大排列的整型数字列表，我们判断某一个数字是不是在这个列表里面。
nums = [1,3,7,11,22,34,55,78,111,115]
for item in nums:
if item == 10:
print('find it')
break
else:
print('not exists')
#输出：
not exists
not exists
not exists
not exists
not exists
not exists
not exists
not exists
not exists
not exists
from random import randint
nums = [randint(1,100) for i in range(100)]
nums = sorted(nums)
print(nums)
#输出：
[1, 2, 3, 4, 6, 6, 7, 8, 8, 8, 8, 9, 13, 14, 15, 15, 16, 17, 17, 18, 18, 19, 19, 20, 22, 22, 23, 24, 25, 30, 30, 32, 32, 35, 35, 36, 36, 36, 38, 39, 39, 39, 40, 42, 44, 45, 45, 47, 47, 52, 52, 54, 54, 55, 55, 57, 57, 57, 57, 57, 58, 61, 61, 61, 62, 63, 63, 65, 66, 66, 66, 66, 67, 68, 70, 70, 72, 74, 74, 75, 80, 82, 82, 84, 85, 85, 85, 85, 86, 86, 86, 89, 91, 94, 94, 97, 97, 97, 98, 99]
nums = [1, 3, 7, 11, 22, 34, 55, 78, 111, 115]
def search(search_num,nums):
mid_index = len(nums)//2
print(nums)
if not nums:
print('not exists')
if search_num>nums[mid_index]:
nums=nums[mid_index+1:]
search(search_num,nums)
elif search_num<nums[mid_index]:
nums = nums[:mid_index]
search(search_num,nums)
else:
print('find it')
search(7,nums)
#输出：
[1, 3, 7, 11, 22, 34, 55, 78, 111, 115]
[1, 3, 7, 11, 22]
find it