递归(盗梦空间)

1.函数的调用

2.函数的传参

3.函数的返回值

前置条件

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

故事场景

RecursionError

# 修改递归最大深度(没必要)sys.setrecursionlimit(100000000)

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

1.递归要尽量控制次数，如果需要很多层才能解决问题，不适合用递归解决

递归不是万能的

递归比循环更占用内存

2.循环和递归的关系

递归函数要想结束，必须在函数内写一个return，并且return条件必须是一个可达到的条件

3.递归的终止条件

规范

\"\"\"目标：理解阶乘的调用步骤\"\"\"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\"\"\

1.计算阶乘

\"\"\"目标：遍历文件夹下的所有文件，理解执行步骤\"\"\"import osdef show_file(path: str):    \"\"\"    目录下的所有文件    :param path:    :return:    \"\"\

2.os模块：遍历文件夹下的所有文件

\"\"\"目标：计算目录及子目录下所有文件的大小理解递归中函数的值传递\"\"\"import osdef show_file_size(path: str):    \"\"\"    计算目录下所有的文件大小    :param path:    :return:    \"\"\

3.os模块：计算文件夹下所有文件的大小

循环方式

拿到所有数列

拿到第多少个斐波那契数

生成器函数方式

注意：近视递归内调用2个递归

递归方式

\"\"\"目标：计算斐波那契数列继续理解函数的值传递，函数的返回值\"\"\"# 循环def loop_feibo(n: int):    \"\"\"    循环模式计算    :param n:    :return:    \"\"\

代码示例

4.计算斐波那契数列

三级菜单字典

测试数据

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 Trueshow_menu(menu)

综合案例，尽量掌握

5.三级菜单

从一个有序列表中查找值

\"\"\"目标：从有序列表中查找指定元素的索引位置二分查找法\"\"\

循环模式

6.二分查找算法

练习题：

递归(盗梦空间)