面对一个复杂的大问题，我们常说要“化整为零”。但Python的递归函数把它做到了极致：它把问题不断分解，直到变成一个个完全相同的、最简单的小问题。你觉得，这个“最简单的小问题”在递归中扮演着什么关键角色？
如：斐波那契数列，第n位 f(n) = f(n-1) + f(n-2)
第一步：明确这个函数想要干什么（先定义出来，明确调用方式）
# 斐波拉契数列：1、1、2、3、5、8、13、21...def f(n): # 编写递归代码求第n位的结果# 调用函数print(f(15))
第二步：寻找递归的结束条件
# 斐波拉契数列：1、1、2、3、5、8、13、21...def f(n): # 编写递归代码求第n位的结果 if n ==1or n == 2: return1# 调用函数print(f(15))
第三步：找出函数的等价关系式(最关键的一步)
# 斐波拉契数列：1、1、2、3、5、8、13、21...def f(n): # 编写递归代码求第n位的结果 if n ==1or n == 2: return1 return f(n-1) + f(n-2)# 调用函数print(f(15))
阶乘是什么？一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，如：n!=1×2×3×...×(n-1)×n
1! = 1
2! = 1x2 = 2
3! = 1x2x3 = 6
4! = 1x2x3x4 = 24
...
n!=1×2×3×...×(n-1)×n
第一步：明确这个函数要做什么以及定义函数以及调用方式
def f(n): # 编写递归条件print(f(100))
第二步：寻找递归的结束条件
def f(n): # 编写递归结束条件 if n == 1: return1 # ...递归等式print(f(100))
第三步：编写递归等价公式（自己要调用自己）
等价公式 = 找规律
1! = f(1) = 1
2! = f(2) = 2
3! = f(2)x3 = 6
4! = f(3)x4 = 24
...
n!= f(n-1) * n
def f(n): # 编写递归结束条件 if n == 1: return1 # ...递归等式 return f(n-1) * nprint(f(100))
猴子吃桃问题：猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时，就只剩下一个桃子了。求第1天共摘了多少个桃子？
第一步：确定函数主要要完成什么功能，需要传递哪些参数，确认调用方式
分析：
f(10) = 1
f(9) = (f(10)+1)*2 = 4
f(8) = (f(9)+1)*2 = 10
f(7) = (f(8)+1)*2 = 22
...
f(n) = (f(n-1)+1)*2
1:1
2:4 f(2)=(f[1]+1)*2
3:10
...
f(10)=(f[9]+1)*2
递推版本：
def apples(n): if n == 1: return1 dict1 = {1:1, 2:4} for i in range(2, n+1): dict1[i] = (dict1[i-1]+1) * 2 return dict1[n]print(apples(10))
递归版本：
# 第一步：确定函数功能def f(n): # 第二步：编写递归结束条件（出口） if n == 10: return1 # 第三步：寻找与这个问题相似的等价公式 return (f(n+1) + 1) * 2# 调用函数print(f(1))
（缺点，n=1000时，数据会过大，导致程序报错，可以尝试
from functools import lru_cache
@lrc_cache）
今日学习完毕，课后作业：
请编写一个名为 factorial(n)的递归函数，计算并返回非负整数 n的阶乘。
阶乘的定义如下：
（1）如果 n为 0 或 1，则 n! = 1。（这是递归的基准情况）
（2）如果 n大于 1，则 n! = n * (n-1)!。（这是递归的递推关系）
要求：
①函数必须使用递归实现。
②处理输入为 0 的情况。
10个月宝宝每天需要喝多少奶粉？
