递归(盗梦空间)
2023-04-08 15:28:37 7 举报AI智能生成
递归
作者其他创作
大纲/内容
前置条件
1.函数的调用
2.函数的传参
3.函数的返回值
故事场景
假设你在一个电影院，你想知道自己坐在哪一排，但是前面人很多，你懒得去数了，于是你问前一排的人「你坐在哪一排？」，这样前面的人 (代号 A) 回答你以后，你就知道自己在哪一排了——只要把 A 的答案加一，就是自己所在的排了。不料 A 比你还懒，他也不想数，于是他也问他前面的人 B「你坐在哪一排？」，这样 A 可以用和你一模一样的步骤知道自己所在的排。然后 B 也如法炮制。直到他们这一串人问到了最前面的一排，第一排的人告诉问问题的人「我在第一排」。最后大家就都知道自己在哪一排了。
递归最大深度1000层：
为了节省内存空间，不要让用户无限使用内存空间
为了节省内存空间，不要让用户无限使用内存空间
RecursionError
# 修改递归最大深度(没必要)
sys.setrecursionlimit(100000000)
sys.setrecursionlimit(100000000)
规范
1.递归要尽量控制次数，如果需要很多层才能解决问题，不适合用递归解决
2.循环和递归的关系
递归不是万能的
递归比循环更占用内存
3.递归的终止条件
递归函数要想结束，必须在函数内写一个return，并且return条件必须是一个可达到的条件
练习题：
1.计算阶乘
"""
目标：理解阶乘的调用步骤
"""
def func(n: int):
"""
计算 1～n的阶乘
:param n:
:return:
"""
if n == 1:
return n
else:
return n * func(n - 1)
ret = func(5)
print(ret) # 120
"""
# 执行步骤
def func(5): # 第一层 n = 5
if 5 == 1:
return n
else:
return 5 * func(5 - 1) # return 5 * func(4) 注意：此时就要开始调用func本身了 # 递归返回 return 5 * 4 3 * 2 * 1, 此时最外层函数也执行完毕了，结果返回给递归调用方
def func(4):
if 4 == 1:
return n
else:
return 4 * func(4 - 1) # return 4 * func(3) # 递归返回 return 4 * 3 * 2 * 1
def func(3):
if 3 == 1:
return n
else:dbnq
7
return 3 * func(3 - 1) # return 3 * func(2) # 递归返回 return 3 * 2 * 1
def func(2):
if 2 == 1:
return n
else:
return 2 * func(2 - 1) # return 2 * func(1) # 递归返回 return 2 * 1
def func(1):
if 1 == 1:
return n # 此时 n == 1: retrun 1 本层递归执行结束，返回上一层，返回值给上一曾的 func(1)
else:
return n * func(n - 1)
"""
目标：理解阶乘的调用步骤
"""
def func(n: int):
"""
计算 1～n的阶乘
:param n:
:return:
"""
if n == 1:
return n
else:
return n * func(n - 1)
ret = func(5)
print(ret) # 120
"""
# 执行步骤
def func(5): # 第一层 n = 5
if 5 == 1:
return n
else:
return 5 * func(5 - 1) # return 5 * func(4) 注意：此时就要开始调用func本身了 # 递归返回 return 5 * 4 3 * 2 * 1, 此时最外层函数也执行完毕了，结果返回给递归调用方
def func(4):
if 4 == 1:
return n
else:
return 4 * func(4 - 1) # return 4 * func(3) # 递归返回 return 4 * 3 * 2 * 1
def func(3):
if 3 == 1:
return n
else:dbnq
7
return 3 * func(3 - 1) # return 3 * func(2) # 递归返回 return 3 * 2 * 1
def func(2):
if 2 == 1:
return n
else:
return 2 * func(2 - 1) # return 2 * func(1) # 递归返回 return 2 * 1
def func(1):
if 1 == 1:
return n # 此时 n == 1: retrun 1 本层递归执行结束，返回上一层，返回值给上一曾的 func(1)
else:
return n * func(n - 1)
"""
2.os模块：遍历文件夹下的所有文件
"""
目标：遍历文件夹下的所有文件，理解执行步骤
"""
import os
def show_file(path: str):
"""
目录下的所有文件
:param path:
:return:
"""
names = os.listdir(path)
file_list = []
for name in names:
abs_path = os.path.join(path, name)
if os.path.isfile(abs_path):
file_list.append(name)
else:
file_list += show_file(abs_path) # 递归之后将每一层的file_list累加，将累加后的结果return给上一层调用方
return file_list
if __name__ == '__main__':
path = "/home/zew/PycharmProjects/R2CodingForPython/"
ret = show_file(path)
print(ret)
目标：遍历文件夹下的所有文件，理解执行步骤
"""
import os
def show_file(path: str):
"""
目录下的所有文件
:param path:
:return:
"""
names = os.listdir(path)
file_list = []
for name in names:
abs_path = os.path.join(path, name)
if os.path.isfile(abs_path):
file_list.append(name)
else:
file_list += show_file(abs_path) # 递归之后将每一层的file_list累加，将累加后的结果return给上一层调用方
return file_list
if __name__ == '__main__':
path = "/home/zew/PycharmProjects/R2CodingForPython/"
ret = show_file(path)
print(ret)
3.os模块：计算文件夹下所有文件的大小
"""
目标：计算目录及子目录下所有文件的大小
理解递归中函数的值传递
"""
import os
def show_file_size(path: str):
"""
计算目录下所有的文件大小
:param path:
:return:
"""
sum_file_size = 0
file_list = os.listdir(path)
for name in file_list:
abs_path = os.path.join(path, name)
if os.path.isfile(abs_path):
sum_file_size += os.path.getsize(abs_path)
else:
sum_file_size += show_file_size(abs_path) # 每次递归，都会return当前文件夹内的文件大小之和，再累加
return sum_file_size
if __name__ == '__main__':
path = "/home/zew/PycharmProjects/R2CodingForPython/day21_递归习题讲解、shutil、logging模块/exam"
ret = show_file_size(path)
print(ret)
目标：计算目录及子目录下所有文件的大小
理解递归中函数的值传递
"""
import os
def show_file_size(path: str):
"""
计算目录下所有的文件大小
:param path:
:return:
"""
sum_file_size = 0
file_list = os.listdir(path)
for name in file_list:
abs_path = os.path.join(path, name)
if os.path.isfile(abs_path):
sum_file_size += os.path.getsize(abs_path)
else:
sum_file_size += show_file_size(abs_path) # 每次递归，都会return当前文件夹内的文件大小之和，再累加
return sum_file_size
if __name__ == '__main__':
path = "/home/zew/PycharmProjects/R2CodingForPython/day21_递归习题讲解、shutil、logging模块/exam"
ret = show_file_size(path)
print(ret)
4.计算斐波那契数列
循环方式
生成器函数方式
拿到所有数列
拿到第多少个斐波那契数
递归方式
注意：近视递归内调用2个递归
代码示例
"""
目标：计算斐波那契数列
继续理解函数的值传递，函数的返回值
"""
# 循环
def loop_feibo(n: int):
"""
循环模式计算
:param n:
:return:
"""
a, b = 1, 1
if n == 1 or n == 2:
return b
else:
while n > 2:
a, b = b, a+b
n -= 1
return b
# 递归
def feibo(n: int, a=1, b=1):
"""
计算第n个斐波那契数 1 1 2 3 5 8 13 21..
:param n:
:return:
"""
if n == 1 or n == 2:
return b
else:
a, b = b, a+b
return feibo(n-1, a, b)
"""
递归执行步骤
def feibo(5: int, a=1, b=1):
if 5 == 1 or 5 == 2:
return b
else:
a, b = 1, 1+1
return feibo(n-1, a, b) # feibo(5-1, 1, 1+1) -> feibo(n=4, a=1, b=2) ; 最外层函数结束，返回值返回给递归函数调用方
def feibo(4: int, a=1, b=2):
if 4 == 1 or 4 == 2:
return b
else:
a, b = 2, 1+2
return feibo(n-1, a, b) # feibo(4-1, 2, 3) -> feibo(n=3, a=2, b=3) ; b = 5
def feibo(3: int, a=2, b=3):
if n == 1 or n == 2:
return b
else:
a, b = 3, 2+3
return feibo(n-1, a, b) # feibo(3-1, 3, 5) -> feibo(n=2, a=3, b=5) ; 此时n=2,向上return返回值 b=5
def feibo(n: int, a=1, b=1):
if n == 1 or n == 2:
return b
else:
a, b = b, a+b
return feibo(n-1, a, b)
ret = feibo(5)
"""
# 通过yield 生成器，生成1~n个非波那契数列
def feibo_yield(n: int):
a, b = 1, 1
if n == 1:
yield 1
else:
yield from (1, 1)
while n > 2:
a, b = b, a+b
yield b
n -= 1
if __name__ == '__main__':
ret = loop_feibo(8)
print(ret)
ret = feibo(8)
print(ret)
ret = feibo_yield(8)
print(list(ret))
目标：计算斐波那契数列
继续理解函数的值传递，函数的返回值
"""
# 循环
def loop_feibo(n: int):
"""
循环模式计算
:param n:
:return:
"""
a, b = 1, 1
if n == 1 or n == 2:
return b
else:
while n > 2:
a, b = b, a+b
n -= 1
return b
# 递归
def feibo(n: int, a=1, b=1):
"""
计算第n个斐波那契数 1 1 2 3 5 8 13 21..
:param n:
:return:
"""
if n == 1 or n == 2:
return b
else:
a, b = b, a+b
return feibo(n-1, a, b)
"""
递归执行步骤
def feibo(5: int, a=1, b=1):
if 5 == 1 or 5 == 2:
return b
else:
a, b = 1, 1+1
return feibo(n-1, a, b) # feibo(5-1, 1, 1+1) -> feibo(n=4, a=1, b=2) ; 最外层函数结束，返回值返回给递归函数调用方
def feibo(4: int, a=1, b=2):
if 4 == 1 or 4 == 2:
return b
else:
a, b = 2, 1+2
return feibo(n-1, a, b) # feibo(4-1, 2, 3) -> feibo(n=3, a=2, b=3) ; b = 5
def feibo(3: int, a=2, b=3):
if n == 1 or n == 2:
return b
else:
a, b = 3, 2+3
return feibo(n-1, a, b) # feibo(3-1, 3, 5) -> feibo(n=2, a=3, b=5) ; 此时n=2,向上return返回值 b=5
def feibo(n: int, a=1, b=1):
if n == 1 or n == 2:
return b
else:
a, b = b, a+b
return feibo(n-1, a, b)
ret = feibo(5)
"""
# 通过yield 生成器，生成1~n个非波那契数列
def feibo_yield(n: int):
a, b = 1, 1
if n == 1:
yield 1
else:
yield from (1, 1)
while n > 2:
a, b = b, a+b
yield b
n -= 1
if __name__ == '__main__':
ret = loop_feibo(8)
print(ret)
ret = feibo(8)
print(ret)
ret = feibo_yield(8)
print(list(ret))
5.三级菜单
测试数据
三级菜单字典
menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
}
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
}
综合案例，尽量掌握
def show_menu(menu: dict):
"""
三级菜单
:param menu:
:return:
"""
while True:
for city in menu:
print(city)
key = input('>>>')
if menu.get(key):
dic = menu[key]
flag = show_menu(dic)
if not flag:
return False
elif key.upper() == 'Q':
return False
elif key.upper() == 'B':
return True
show_menu(menu)
"""
三级菜单
:param menu:
:return:
"""
while True:
for city in menu:
print(city)
key = input('>>>')
if menu.get(key):
dic = menu[key]
flag = show_menu(dic)
if not flag:
return False
elif key.upper() == 'Q':
return False
elif key.upper() == 'B':
return True
show_menu(menu)
6.二分查找算法
从一个有序列表中查找值
循环模式
"""
目标：从有序列表中查找指定元素的索引位置
二分查找法
"""
def binary_lockup(data_list: list, n: int):
"""
从有许列表中查找数值n的索引位置
:param data_list: 有序列表
:param n: 数值n
:return: n的索引位置
"""
top = 0
end = len(data_list) - 1
index = -1
while top <= end:
mid = int((top + end) / 2)
if n == data_list[mid]:
index = mid
break
elif data_list[mid] > n:
end = mid - 1
elif data_list[mid] < n:
top = mid + 1
return index
if __name__ == '__main__':
while 1:
value = int(input('>>>'))
data = [i ** 2 for i in range(11)]
ret = binary_lockup(data, value)
print(f'index: {ret}, data[ret] = {data[ret]}')
目标：从有序列表中查找指定元素的索引位置
二分查找法
"""
def binary_lockup(data_list: list, n: int):
"""
从有许列表中查找数值n的索引位置
:param data_list: 有序列表
:param n: 数值n
:return: n的索引位置
"""
top = 0
end = len(data_list) - 1
index = -1
while top <= end:
mid = int((top + end) / 2)
if n == data_list[mid]:
index = mid
break
elif data_list[mid] > n:
end = mid - 1
elif data_list[mid] < n:
top = mid + 1
return index
if __name__ == '__main__':
while 1:
value = int(input('>>>'))
data = [i ** 2 for i in range(11)]
ret = binary_lockup(data, value)
print(f'index: {ret}, data[ret] = {data[ret]}')
0 条评论
下一页
