我们知道，在函数内部可以调用其他函数。

递归函数是指在一个函数内部调用函数本身。

我们可以使用递归函数做什么呢？

比如计算阶乘， n! = 1 * 2 * 3 *... * n-1 * n

若用fact(n) 表示为 n!
则其实fact(n-1)便是 (n-1)!
而n! = n x (n-1)!
因此 fact(n) = fact(n-1)

再考虑特殊情况，fact(1) = 1。因此除fact(1)以外，所有的fact(n) 都可以表示为n 乘以它的前一项，而前一项也可以表示为，fact(n-1)乘以它的前一项，以次类推，便可以递归下去。

而递归函数正是利用了这种思想。

因此我们来构建一下fact(n)函数。

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

# 测试
print(fact(3))

具体的运算过程便是之前提到的递归过程。

理论上来说，所有的递归函数都可以用循环的方式，但循环不如递归清晰。

def fact_2(n):
    sum = 1
    while n > 1:
        sum = sum * n
        n = n - 1
    return sum

递归函数的栈溢出问题

当我们使用fact(1000) 时，会发现程序报错了。这是为什么呢？

RecursionError: maximum recursion depth exceeded in comparison

可以用栈溢出来解释。

在计算机中，函数调用是通过栈(stack) 这一结构实现的，每当一个函数调用一次，栈就会加一层栈帧；每当函数返回一次，栈就会减少一层栈帧。由于设定的栈的大小是有限的，因此当调用函数次数过多时，会导致栈的大小超出限制，也叫栈溢出。因而fact(1000)会报错。但fact_2(1000)却不会。

解决栈溢出的方法

栈溢出可以通过尾递归优化的方式予以解决。

尾递归是指，在函数返回的时候，调用自身，且return中不可以包含表达式。

从而解释器会将尾递归优化，使其无论被调用多少次，都只会占用一个栈。

为什么之前的函数会溢出，因为其返回的值中引入了乘法表达式。

因此，我们可以通过多定义一个函数的方式，实现尾递归，从而解决栈溢出的问题。

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)

汉诺塔问题

汉诺塔的规则，实际就是有三个柱子ABC。现在A柱子上有n个圆盘，圆盘面积由小到大依次排列往下。
现在需要将A柱子上的n个圆盘，按照相同排列顺序，移动到C柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。需要给出最佳移动路径。

# -*- coding: utf-8 -*-

# 请编写move(n, a, b, c)函数，它接收参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，
# 然后打印出把所有盘子从A借助B移动到C的方法。

def move(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        move(n-1, a, c, b)
        print(a, '-->', c)
        move(n-1, b, a, c)

move(3, 'a', 'b', 'c')

还可以通过使用全局变量，加上计次功能。

# -*- coding: utf-8 -*-

# 请编写move(n, a, b, c)函数，它接收参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，
# 然后打印出把所有盘子从A借助B移动到C的方法。
count = 0

def move(n, a, b, c):
    global count
    if n == 0:
        print('0')
    elif n == 1:
        print(a, '-->', c)
        count += 1
    else:
        move(n-1, a, c, b)
        print(a, '-->', c)
        count += 1
        move(n-1, b, a, c)
    return count

move(6, 'a', 'b', 'c')
print(count)

思路

汉诺塔问题，本质就是一个递归问题。
考虑有三个柱子，a，b，c，n表示a柱子上的圆环个数。
用 xx -> xx 表示移动路径，如 a -> b，表示a 移动到b上。

首先考虑 n = 1，不用想的，a -> c。
接着考虑最简单的n = 2 的情况。就是将 a -> b , a->c , b -> c。似乎找不到什么规律。
接着来，n = 3。就是 a ->c, a ->b, c ->b，非常巧合的是，此时b 上的两个圆环正好跟a 时的圆环要求顺序一样，只是此时 圆环在b 而不在c上，因为我们还有第三个圆环的缘故。这时候如果你再将a -> c，即将最大的圆环先移动到c上。此时你又惊讶的发现，如果你此时不考虑c上的圆环，那么问题又回到了n = 2时，而从本质上来说，此时c上最大的圆环已经不用移动了，实际也就是如何利用a 将b 上的圆环移动到c上。只不过，和n = 2不同的是，现在需要将 b 上的圆环移动到c上。
按照这样的思路，思考n = 2，其实本质也是一样， a ->b，也是 n = 1时的问题，只是此时的 b和c 互换了；再进行 a -> c；再进行 b ->c，只是此时的 a和c 互换了。

而同样的你可以想想n = 4，甚至任意值的时候的情况，其实也无非就是这三步：
第一步，将 n 的问题划为 n-1的问题，只是这时候移动到b 而不是c；
第二步，将最大的圆环从a 移动到c；
第三步，将b 上的n-1的圆环，按 n-1 的处理办法移动到c。

那么如何解决n-1的问题呢？
还是这三步，依次往复，不断递归，直到 n = 1。

用代码来表示便是

def move(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        move(n-1, a, c, b) # 第一步，b 和 c 互换了
        print(a, '-->', c) # 第二步，最大的先去c
        move(n-1, b, a, c) # 第三步，a 和 b 互换了

如果完全理解了上面的思路，相信你也很快能够想到一共需要移动多少次这个问题的答案了。

解决汉诺塔的计数

其本质便是一个等比数列。

ps：如果你实在还是不太明白的话，可以取一个简单一点的数，来捋一遍函数运行的过程，即 a、b，b、c 这些参数互换的过程，会好理解一些。