# 递归函数

fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n

``````def fact(n):
if n==1:
return 1
return n * fact(n - 1)
``````

``````>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
``````

``````===> 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
``````

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

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

`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标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。

## 练习

``````def move(n, a, b, c):

pass

# 期待输出:
# A --> C
# A --> B
# C --> B
# A --> C
# B --> A
# B --> C
# A --> C
move(3, 'A', 'B', 'C')
``````

recur.py