函数内部可以调用其他函数。如果一个函数调用自己，那就是递归函数了。
拿计算阶乘来说，n! = 1 × 2 × 3 × ... × n。写个 fact(n) 函数，你会发现一个规律：
fact(n)=n!=1×2×3×⋅⋅⋅×(n−1)×n=(n−1)!×n=fact(n−1)×n
也就是 fact(n) 可以表示成 n × fact(n-1)，只有 n=1 时需要单独处理。
递归写法很直接：
def fact(n):
if n==1:
return 1
return n * fact(n - 1)
跑一下试试：
>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
算 fact(5) 的时候，函数调用过程是这样的：
=> fact(5)
=> 5 * fact(4)
=> 5 * (4 * fact(3))
=> 5 * (4 * (3 * fact(2)))
=> 5 * (4 * (3 * (2 * fact(1))))
=> 5 * (4 * (3 * (2 * 1)))
=> 5 * (4 * (3 * 2))
=> 5 * (4 * 6)
=> 5 * 24
=> 120
递归的好处是定义简单、逻辑清晰。所有递归函数都能改成循环写法，但循环的逻辑往往不如递归清楚。
用递归要小心栈溢出。计算机里函数调用靠栈（stack）这种数据结构实现，每进入一个函数调用就加一层栈帧，函数返回就减一层。栈的大小有限，递归调用太多次就会把栈撑爆。试试 fact(1000)：
>>> fact(1000)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 4, in fact
...
File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison
怎么解决栈溢出？用尾递归优化。尾递归和循环效果一样，可以把循环看成是特殊的尾递归。
尾递归指的是函数返回时调用自己，而且 return 语句不能包含表达式。这样编译器或解释器就能优化，让递归无论调多少次都只占一个栈帧，不会溢出。
上面的 fact(n) 因为 return n * fact(n - 1) 有乘法表达式，不是尾递归。要改成尾递归，得多写点代码，把每一步的乘积传进递归函数：
def fact(n):
return fact_iter(n, 1)
def fact_iter(num, product):
if num == 1:
return product
return fact_iter(num - 1, num * product)
看到没？return fact_iter(num - 1, num * product) 只返回递归函数本身，num - 1 和 num * product 在调用前就算好了，不影响函数调用。
fact(5) 对应的 fact_iter(5, 1) 调用过程：
=> fact_iter(5, 1)
=> fact_iter(4, 5)
=> fact_iter(3, 20)
=> fact_iter(2, 60)
=> fact_iter(1, 120)
=> 120
尾递归调用时如果做了优化，栈不会增长，调多少次都不会溢出。
但问题来了——大多数编程语言没做尾递归优化，Python解释器也没做。所以即使把 fact(n) 改成尾递归，照样会栈溢出。
练习
汉诺塔的移动用递归函数特别好实现。
写个 move(n, a, b, c) 函数，参数 n 表示第一个柱子A上的盘子数量，然后打印出把所有盘子从A借助B移到C的方法：
def move(n, a, b, c):
if n == 1:
print(a, '-->', c)
# 期待输出:
# A --> C
# A --> B
# C --> B
# A --> C
# B --> A
# B --> C
# A --> C
move(3, 'A', 'B', 'C')
小结
递归函数的优点是逻辑简单清晰，缺点是调用太深会导致栈溢出。
支持尾递归优化的语言可以通过尾递归防止栈溢出。尾递归和循环其实等价，没有循环语句的编程语言只能靠尾递归实现循环。
Python标准解释器没做尾递归优化，任何递归函数都有栈溢出的风险。