廖雪峰 | 3.2 递归函数

1，定义
一个函数在内部调用自身本身，这个函数就是递归函数。
例如，计算阶乘n! = 1 x 2 x 3 x ... x n

>>> def fact(n):
...     if n == 1:
...         return 1
...     return n*fact(n-1)
...
>>> fact(1)
1
>>> fact(3)
6

2，栈溢出
（1）栈溢出，stack overflow，递归调用的次数过多，会导致栈溢出。例如，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
  File "<stdin>", line 4, in fact
  [Previous line repeated 995 more times]
  File "<stdin>", line 2, in fact
RecursionError: maximum recursion depth exceeded in comparison

（2）尾递归优化，是解决递归调用栈溢出的方法。

• 尾递归是指，在函数返回的时候，调用自身本身，并且，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)

fact(100)#依旧报错

• 尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。
• 遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上面的fact(n)函数改成尾递归方式，也会导致栈溢出。
  3，练习：汉诺塔游戏
  请编写move(n, a, b, c)函数，它接收参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，然后打印出把所有盘子从A借助B移动到C的方法，例如：

# -*- coding: utf-8 -*-
def hanoi(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        hanoi(n-1, a, b, c)
        print(a, '-->', c)
        hanoi(n-1, b, a, c)

#测试
>>> from hanoi import hanoi
>>> hanoi(3, 'A', 'B', 'C')
A --> C
A --> C
B --> C
A --> C
B --> C
B --> C
A --> C