递归(盗梦空间)

2023-04-08 15:28:37   7  举报





AI智能生成

递归

python

模版推荐

作者其他创作

大纲/内容

前置条件

1.函数的调用

2.函数的传参

3.函数的返回值

故事场景

假设你在一个电影院，你想知道自己坐在哪一排，但是前面人很多，你懒得去数了，于是你问前一排的人「你坐在哪一排？」，这样前面的人 (代号 A) 回答你以后，你就知道自己在哪一排了——只要把 A 的答案加一，就是自己所在的排了。不料 A 比你还懒，他也不想数，于是他也问他前面的人 B「你坐在哪一排？」，这样 A 可以用和你一模一样的步骤知道自己所在的排。然后 B 也如法炮制。直到他们这一串人问到了最前面的一排，第一排的人告诉问问题的人「我在第一排」。最后大家就都知道自己在哪一排了。

递归最大深度1000层： 为了节省内存空间，不要让用户无限使用内存空间

RecursionError

# 修改递归最大深度(没必要) 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)        """

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)

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)

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

5.三级菜单

测试数据

三级菜单字典

menu = {     '北京': {         '海淀': {             '五道口': {                 '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)

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]}')